RTEMS | draft: Add POSIX msgq priority bucket + bitmap implementation (!1164)

[Chandan U (@Chandanuvm)]

Chandan U commented on a discussion on cpukit/include/rtems/score/coremsg.h: https://gitlab.rtems.org/rtems/rtos/rtems/-/merge_requests/1164#note_148585

 >    Chain_Control Inactive_messages;
 >  };
 >  
 > +#if defined( RTEMS_POSIX_API ) && ( MQ_PRIO_MAX <= 255 )
 > +typedef struct {
 > +  CORE_message_queue_Control   Base;
 > +  Priority_bit_map_Control     Queue;

Regarding the memory overhead of the message queue priority optimization,

Currently, the solution uses a priority bucket + bitmask for priorities \<= 255, falling back to a linear search for anything higher. While the O(1) fast pathl is ideal for standard ranges, the linear fallback scales poorly for worst case scenarios.

Instead of transitioning to a complete Red-black tree for all queues, which would sacrifice O(1) determinism, In my proposal I have mentioned about keeping the Bucket + Bitmask for \<= 255, and utilizing a Red-black tree strictly as the fallback for priorities \> 255.

Which ensures,

- Strict O(1) performance for the most common POSIX priority ranges (\<=255).
- O(log N) predictable scaling for the remaining cases (\> 255)

Will this solution solve both the memory overhead and time complexity problems ?

-- 
View it on GitLab: https://gitlab.rtems.org/rtems/rtos/rtems/-/merge_requests/1164#note_148585
You're receiving this email because of your account on gitlab.rtems.org.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/bugs/attachments/20260415/11d15c62/attachment-0001.htm>