Message Queue

Overview

XWOS’s message queue (xwmq) is implemented using a doubly circular linked list.

flowchart LR
    Head --> Msg1 --> Head
    Msg1 --> Msg2 --> Msg1
    Msg2 --> Msg3 --> Msg2
    Msg3 --> Msg4 --> Msg3
    Msg4 --> Msg5 --> Msg4
    Msg5 --> Msg6 --> Msg5
    Msg6 --> Msg7 --> Msg6
    Msg7 --> Head --> Msg7

Messages can be sent to the head of the queue or to the tail of the queue. Messages can be received from the head of the queue or from the tail of the queue.

Message Queue Messages

Each node of the message queue is struct xwmq_msg.

struct xwmq_msg {
        void * data;
        xwsq_t topic;
        struct xwlib_bclst_node node;
};

• data: message data, which can only carry a pointer-length amount of data
• topic: message topic, the meaning of which is user-defined
• node: linked list node

Message Slots

Message slots are the message array defined by the user when initializing the message queue. The number of messages in the message queue cannot exceed the number of message slots.

Message Queue Object and Object Descriptor

The message queue object is a derived class of the XWOS object struct xwos_object. Similarly, the message queue object uses the message queue object descriptor xwmq_d to address validity and identity legitimacy issues.

The message queue object descriptor consists of the message queue object pointer and a tag:

typedef struct {
        struct xwmq * mq; /**< pointer to message queue object */
        xwsq_t tik; /**< tag */
} xwmq_d;

When referencing an object through an object descriptor, the value of obj->magic is first checked to see if it is 0x58574F53U, which confirms that the pointer obj points to a valid XWOS object. Then the tag obj->tik is compared with tik to verify the object’s identity. Because an object’s tik is globally unique, when the object is freed, its tik is destructed to 0 by the destructor. When the memory address is reconstructed as a new object, its tik will certainly differ from the object descriptor’s tik.

Limitations

Message queue messages can only carry pointer-length data. If larger data needs to be sent, only the address of the data buffer can be sent. If the data buffer is obtained through dynamic memory allocation, users must be especially careful that the data buffer is not accidentally freed.

Static Initialization and Destruction of Message Queue

• Static initialization: xwmq_init()
  • Static means the user pre-defines thread structure objects, which are allocated memory by the compiler at compile time.
  • When initializing a message queue, a message array must be pre-defined as message slots.

struct xwmq brd_mq;
struct xwmq_msg brd_mq_txq[16]; // up to 16 messages


xwer_t brd_init_xwmq(void)
{
        return xwmq_init(&brd_mq, brd_mq_txq, xw_array_size(brd_mq_txq));
}

• Destruction of statically initialized semaphore: xwmq_fini()

Dynamic Creation and Deletion of Message Queue

XWOS does not provide CAPI for dynamic memory-based creation and deletion.

Sending Messages

Enqueue

Enqueue means sending a message to the tail of the message queue. Before sending, an available message slot must be obtained.

• xwmq_eq(): wait for a message slot, can only be used in thread context
• xwmq_eq_to(): timed wait for a message slot, can only be used in thread context
• xwmq_eq_unintr(): uninterruptible wait for a message slot, can only be used in thread context
• xwmq_tryeq(): try to obtain a message slot, can be used in any context

Jump Queue

Jump queue means sending a message to the head of the message queue. Before sending, an available message slot must be obtained.

• xwmq_jq(): wait for a message slot, can only be used in thread context
• xwmq_jq_to(): timed wait for a message slot, can only be used in thread context
• xwmq_jq_unintr(): uninterruptible wait for a message slot, can only be used in thread context
• xwmq_tryjq(): try to obtain a message slot, can be used in any context

Receiving Messages

Head Dequeue

Head dequeue means receiving a message from the head of the message queue. After receiving, a message slot is freed. If there are sending threads waiting for message slots, they will be woken.

• xwmq_dq(): wait for a message, can only be used in thread context
• xwmq_dq_to(): timed wait for a message, can only be used in thread context
• xwmq_dq_unintr(): uninterruptible wait for a message, can only be used in thread context
• xwmq_trydq(): try to obtain a message, can be used in any context

Tail Dequeue

Tail dequeue means receiving a message from the tail of the message queue. After receiving, a message slot is freed. If there are sending threads waiting for message slots, they will be woken.

• xwmq_rq(): wait for a message, can only be used in thread context
• xwmq_rq_to(): timed wait for a message, can only be used in thread context
• xwmq_rq_unintr(): uninterruptible wait for a message, can only be used in thread context
• xwmq_tryrq(): try to obtain a message, can be used in any context

Lifecycle Management of Message Queue Objects

The message queue object’s base class is the XWOS object struct xwos_object. The message queue object also has two sets of lifecycle management CAPI:

• Lifecycle management CAPI accessed via object pointer: requires ensuring that the object is definitely valid when calling CAPI, and that there is no free-and-reallocate scenario where it becomes another object.

  • xwmq_grab(): increase reference count.
  • xwmq_put(): decrease reference count; when the reference count drops to 0, the garbage collection function is called to free the object.

• Lifecycle management CAPI accessed via object descriptor: used when the user cannot guarantee the object is valid or cannot guarantee the object won’t become another object.

  • xwmq_acquire(): verify the object is valid and legitimate through the object descriptor, then increase reference count.
  • xwmq_release(): verify the object is valid and legitimate through the object descriptor, then decrease reference count. When the reference count drops to 0, the garbage collection function is called to free the object.

CAPI Reference

• Header <xwmd/isc/xwmq.h>