The Hidden Optimization in Message Queues — MSG_BARRIER's Lock-Free Fast Path

System V message queues are often dismissed as "legacy technology" — slow, outdated, replaced by POSIX message queues or Unix domain sockets. But this reputation is undeserved. Modern Linux kernels have optimized message queues with lock-free receive paths, atomic operations, and clever memory ordering that make them surprisingly fast.

The key optimization: pipelined_send() uses smp_store_release() to publish a message, and the receiver uses READ_ONCE() to check if a message has arrived — all without taking the queue lock. Only when the message hasn't arrived yet does the kernel fall back to the slow path (sleeping on a wait queue).

This article walks through the message queue source in ipc/msg.c to explain the lock-free fast path, the MSG_BARRIER flag, and the semaphore undo mechanism.

Key Takeaways

• Message queue receive has a lock-free fast path using READ_ONCE(r_msg)
• smp_store_release() publishes messages, READ_ONCE() reads them
• MSG_BARRIER: receiver checks if message arrived without taking lock
• Semaphore undo (sem_undo) auto-rolls-back on process exit
• use_global_lock: degrades to global lock under high contention to prevent livelock
• IPC ID encoding: index + sequence number in single int prevents reuse races

The Myth: "Message Queues are Slow Legacy Technology"

The mental model: msgrcv() takes queue lock → scans message list → copies data → releases lock. This is wrong for the common case.

What actually happens:

  msgrcv(qid, &msg, sizeof(msg), type, IPC_NOWAIT)
       │
       ▼
  ┌─────────────────────────────────────────────────────────────────────┐
  │ Fast Path (lock-free!)                                              │
  │ • Check msg_receiver->r_msg with READ_ONCE()                        │
  │ • If r_msg != NULL: message already there!                          │
  │ • Copy data, return immediately — NO LOCK TAKEN                     │
  └─────────────────────────────────────────────────────────────────────┘
       │ (if r_msg == NULL, message not yet arrived)
       ▼
  ┌─────────────────────────────────────────────────────────────────────┐
  │ Slow Path (locked)                                                  │
  │ • Take queue lock (ipc_lock_object())                               │
  │ • Scan message list for matching type                               │
  │ • If found: copy and return                                         │
  │ • If not: add to waiters list, sleep                                │
  └─────────────────────────────────────────────────────────────────────┘

The Lock-Free Fast Path: pipelined_send()

Publishing a Message

// ipc/msg.c — pipelined_send()
static inline int pipelined_send(struct msqid_ds *msq, struct msg_msg *msg)
{
    struct msg_receiver *r;
 
    // Find the first waiting receiver
    list_for_each_entry(r, &msq->q_receivers, r_list) {
        if (testmsg(r, msg->m_type, mode)) {
            // Publish the message with release semantics
            // This is the key: smp_store_release() ensures all writes
            // to the message are visible before r_msg is set
            smp_store_release(&r->r_msg, msg);
 
            // Wake up the receiver
            wake_up_interruptible(&r->r_wait);
            return 1;
        }
    }
    return 0;  // No matching receiver
}

Receiving a Message

// ipc/msg.c — do_msgrcv()
static long do_msgrcv(int msqid, struct msg_msg *msg, size_t msgsz,
                      long msgtyp, int msgflg, int mode)
{
    struct msg_receiver *r;
    struct msqid_ds *msq;
 
    // Fast path: check if message already arrived
    r = current->r_msg;
    if (r) {
        // Lock-free check!
        struct msg_msg *msg_ptr = READ_ONCE(r->r_msg);
        if (msg_ptr) {
            // Message is here — copy and return (no lock!)
            return do_msg_copy(msg_ptr, msg, msgsz, mode);
        }
    }
 
    // Slow path: take lock and scan
    msq = ipc_lock_check(msqid);
    if (!msq)
        return -EIDRM;
 
    // Scan message list
    msg = find_msg(msq, msgtyp, mode);
    if (msg) {
        ipc_unlock(msq);
        return do_msg_copy(msg, msg, msgsz, mode);
    }
 
    // No message — sleep
    list_add_tail(&r->r_list, &msq->q_receivers);
    ipc_unlock(msq);
 
    // Wait for message
    schedule();
 
    return ret;
}

MSG_BARRIER Flag

The MSG_BARRIER flag allows a receiver to check if a message has arrived without taking the queue lock:

// ipc/msg.c — testmsg()
static int testmsg(struct msg_receiver *r, long type, int mode)
{
    struct msg_msg *msg = READ_ONCE(r->r_msg);
 
    if (msg && (msg->m_type == type || type == 0))
        return 1;  // Message matches!
 
    return 0;
}

This is a single atomic load instruction — no lock, no cache line bouncing.

Semaphore Undo Mechanism

System V semaphores (used internally by message queues) have an undo mechanism for crash safety:

// ipc/sem.c
struct sem_undo {
    struct list_head list_proc;     // Per-process list
    struct list_head list_id;       // Per-semaphore-array list
    int semid;                      // Semaphore array ID
    short *semadj;                  // Per-semaphore adjustment values
};
 
// On process exit, automatically undo all semaphore operations
void exit_sem(struct task_struct *tsk)
{
    struct sem_undo *undo;
 
    // Process all undo entries
    list_for_each_entry(undo, &tsk->sysvsem.undo_list, list_proc) {
        struct sem_array *sma = sem_obtain_object(undo->semid);
        for (int i = 0; i < sma->sem_nsems; i++) {
            // Undo the adjustment
            sma->sem_base[i].semval += undo->semadj[i];
        }
    }
}

This ensures that if a process crashes while holding a semaphore, the semaphore is automatically restored to its previous value.

Deep Detail: IPC ID Encoding

IPC IDs encode both an index and a sequence number in a single int:

// ipc/util.h
#define IPC_SEQ_SHIFT 14
#define IPC_SEQ_MASK  ((1 << IPC_SEQ_SHIFT) - 1)
 
// ID format: [sequence (18 bits)][index (14 bits)]
static inline int ipc_buildid(int id, int seq)
{
    return (seq << IPC_SEQ_SHIFT) | (id & IPC_SEQ_MASK);
}
 
static inline int ipc_getidx(int id)
{
    return id & IPC_SEQ_MASK;
}

This prevents ID reuse races: when an IPC object is destroyed and a new one gets the same index, the sequence number differs, so stale references are detected via ipc_checkid().

How to Observe Message Queue Behavior

Using bpftrace

#!/usr/bin/env bpftrace
// trace_msgq.bt
 
kprobe:ksys_msgsnd
{
    @msgsnd[comm] = count();
}
 
kprobe:do_msgrcv
{
    @msgrcv[comm] = count();
}
 
kprobe:pipelined_send
{
    @pipelined[comm] = count();
}

Using /proc and ipcs

// System V message queues
ipcs -q
 
// Per-queue details
cat /proc/sysvipc/msg
 
// Message queue limits
cat /proc/sys/kernel/msgmax
cat /proc/sys/kernel/msgmnb
cat /proc/sys/kernel/msgmni

Frequently Asked Questions

What is the difference between System V and POSIX message queues?

System V uses msgget()/msgsnd()/msgrcv(). POSIX uses mq_open()/mq_send()/mq_receive(). System V has the lock-free fast path; POSIX has a simpler API.

When should I use message queues vs other IPC?

Use message queues when you need typed messages (different message types in the same queue) or priority-based delivery. Use Unix domain sockets for stream-oriented communication.

What is MSG_NOERROR?

When the received message is larger than the buffer, MSG_NOERROR truncates the message instead of returning an error.

What is use_global_lock?

Under high contention, the kernel falls back to a global lock to prevent livelock. This is a performance optimization for heavily loaded systems.

How do I remove a message queue?

Use msgctl(qid, IPC_RMID, NULL) to remove a queue immediately, or mark it for deletion when the last process detaches.

Conclusion

System V message queues are not slow legacy technology — they have a lock-free fast path using READ_ONCE() and smp_store_release(). The common case (message already available) requires no lock at all. Only when the message hasn't arrived yet does the kernel take the queue lock and sleep.

For production systems, the practical takeaways are: message queues have a lock-free fast path, MSG_BARRIER enables lock-free checking, and the semaphore undo mechanism ensures crash safety.

Sources

• Linux kernel source, ipc/msg.c, pipelined_send()
• Linux kernel source, ipc/msg.c, do_msgrcv()
• Linux kernel source, ipc/sem.c, exit_sem()
• Linux kernel source, ipc/util.c, ipc_buildid()
• Linux kernel source, include/linux/msg.h