How is a message queue implemented in the Linux kernel?

Question

I would like to know how Message Queues are implemented in the Linux Kernel.

Answer 1

The Linux kernel (2.6) implements two message queues:
_{(rather 'message lists', as the implementation is done by using a linked list not strictly following the FIFO principle)}

System V IPC messages

The message queue from System V.

A process can invoke msgsnd() to send a message. He needs to pass the IPC identifier of the receiving message queue, the size of the message and a message structure, including the message type and text.

On the other side, a process invokes msgrcv() to receive a message, passing the IPC identifier of the message queue, where the message should get stored, the size and a value t.

t specifies the message returned from the queue, a positive value means the first message with its type equal to t is returned, a negative value returns the last message equal to type t and zero returns the first message of the queue.

Those functions are defined in include/linux/msg.h and implemented in ipc/msg.c

There are limitations upon the size of a message (max), the total number of messages (mni) and the total size of all messages in the queue (mnb):

$ sysctl kernel.msg{max,mni,mnb}
kernel.msgmax = 8192
kernel.msgmni = 1655
kernel.msgmnb = 16384

The output above is from a Ubuntu 10.10 system, the defaults are defined in msg.h.

More incredibly old System V message queue stuff explained here.

POSIX Message Queue

The POSIX standard defines a message queue mechanism based on System V IPC's message queue, extending it by some functionalities:

• Simple file-based interface to the application
• Support for message priorities
• Support for asynchronous notification
• Timeouts for blocking operations

See ipc/mqueue.c

Example

util-linux provides some programs for analyzing and modifying message queues and the POSIX specification gives some C examples:

Create a message queue with ipcmk; generally you would do this by calling C functions like ftok() and msgget():

$ ipcmk -Q

Lets see what happened by using ipcs or with a cat /proc/sysvipc/msg:

$ ipcs -q

------ Message Queues --------
key        msqid      owner      perms      used-bytes   messages    
0x33ec1686 65536      user       644        0            0           

Now fill the queue with some messages:

$ cat <<EOF >msg_send.c
#include <string.h>
#include <sys/msg.h> 

int main() {
  int msqid = 65536;
  struct message {
    long type;
    char text[20];
  } msg;

  msg.type = 1;
  strcpy(msg.text, "This is message 1");
  msgsnd(msqid, (void *) &msg, sizeof(msg.text), IPC_NOWAIT);
  strcpy(msg.text, "This is message 2");
  msgsnd(msqid, (void *) &msg, sizeof(msg.text), IPC_NOWAIT);

  return 0;
}
EOF

Again, you generally do not hardcode the msqid in the code.

$ gcc -o msg_send msg_send.c
$ ./msg_send
$ ipcs -q

------ Message Queues --------
key        msqid      owner      perms      used-bytes   messages    
0x33ec1686 65536      user       644        40           2        

And the other side, which will be receiving the messages:

$ cat <<EOF >msg_recv.c
#include <stdio.h>
#include <sys/msg.h>

int main() {
  int msqid = 65536;
  struct message {
    long type;
    char text[20];
  } msg;
  long msgtyp = 0;

  msgrcv(msqid, (void *) &msg, sizeof(msg.text), msgtyp, MSG_NOERROR | IPC_NOWAIT);
  printf("%s \n", msg.text);

  return 0;
}
EOF

See what happens:

$ gcc -o msg_recv msg_recv.c
$ ./msg_recv
This is message 1
$ ./msg_recv
This is message 2
$ ipcs -q

------ Message Queues --------
key        msqid      owner      perms      used-bytes   messages    
0x33ec1686 65536      user       644        0            0           

After two receives, the queue is empty again.

Remove it afterwards by specifying the key (-Q) or msqid (-q):

$ ipcrm -q 65536