GSoC '26: Lower Message Priority Range Optimization

Programs Google Summer of Code
1

Hello @gedare @JoelSherrill,

I am currently studying the codebase and relevant documentation to understand the “Lower Message Priority Range Supported by POSIX Message Queues” issue for my GSoC '26 proposal.

Over the last few days, I have been tracing coremsginsert.c, coremsgsubmit.c, coremsgimpl.h, and chainimpl.h, and cross-referencing them with the POSIX and RTEMS API documentation:

  1. POSIX Message Passing Manager: 17. Message Passing Manager — RTEMS POSIX API Guide 7.1023b8c (8th January 2026) documentation
  2. Open Group mq_send / mq_timedsend spec: mq_send
  3. Open Group <mqueue.h> header spec: ]<mqueue.h>
  4. POSIX limits.h view showing _POSIX_MQ_PRIO_MAX = 32:
    limits.h(0p) - Linux manual page

Screenshot (140)
Screenshot (140)860×225 20.1 KB

This confirms that the fixed limit is inserted by the toolchain during compilation and aligns strictly with POSIX standards.

From there, I traced the current O(n) linear scan bottleneck caused by the ordered chain insertion in coremsginsert.c.

its in chainimpl.h

Screenshot (141)
Screenshot (141)895×472 45.4 KB

The while loop is iterating to every node, making it O(n).

I also took time to verify the existing test cases. Initially, I planned to write a separate test file (psxmsgq05) to validate these boundaries. However, after reviewing psxmsgq01, I realized it already covers these scenarios. I ran psxmsgq01 locally and verified it successfully checks all edge cases:

  1. Priorities > MQ_PRIO_MAX are correctly rejected.
  2. Inter-priority insertion (Strict priority ordering, which is currently O(n)).
  3. Intra-priority insertion (FIFO ordering for messages with the exact same priority).

The goal of my proposal will be to design a more efficient insertion algorithm. One suggestion I saw was to use a Red-Black tree, and I am also exploring other optimal solutions like fixed priority buckets that leverage the bounded MQ_PRIO_MAX limit.

Screenshot (143)
Screenshot (143)927×187 22.3 KB

Clearly greater than MQ_PRIO_MAX is not accepted, the time complexity reduction can produce a significant impact.

I look forward to contributing more and would welcome any general advice or feedback on this issue!

2

None of your links work.

3

I think we could go in one of two directions. We could use a red-black tree, or we could enforce that priorities are a power-of-two and we could use the bitmap priority structure from the deterministic priority scheduler.

4

I edited to redirect to the actual page , it was an error with formatting when I pasted the links. Thank You.

  1. 17. Message Passing Manager — RTEMS POSIX API Guide 7.1023b8c (8th January 2026) documentation
  2. mq_send
  3. <mqueue.h>
  4. limits.h(0p) - Linux manual page
5

Thank you for clearing that, since red-black tree’s time complexity is O(log(n)) and also since Max value is 32 we can use bitmap priority where a 32 size array consisting of chains of individual priorities and bitmap of present messages significantly reduces the insertion and deletion time complexity to O(1).