<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html lang="en" style="--code-editor-font: var(--default-mono-font, "GitLab Mono"), JetBrains Mono, Menlo, DejaVu Sans Mono, Liberation Mono, Consolas, Ubuntu Mono, Courier New, andale mono, lucida console, monospace;">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
<title>
GitLab
</title>
<style data-premailer="ignore" type="text/css">
a { color: #1068bf; }
</style>
<style>img {
max-width: 100%; height: auto;
}
body {
font-size: .875rem;
}
body {
-webkit-text-shadow: rgba(255,255,255,.01) 0 0 1px;
}
body {
font-family: "GitLab Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Noto Sans",Ubuntu,Cantarell,"Helvetica Neue",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji"; font-size: inherit;
}
</style>
</head>
<body style="font-size: inherit; -webkit-text-shadow: rgba(255,255,255,.01) 0 0 1px; font-family: "GitLab Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Noto Sans",Ubuntu,Cantarell,"Helvetica Neue",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji";">
<div class="content">
<p style="color: #777777;">
<a href="https://gitlab.rtems.org/Chandanuvm">Chandan U</a>
<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/5247#note_147026">commented</a>:
</p>
<div class="md" style="position: relative; z-index: 1; color: #3a383f; word-wrap: break-word;">
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">Hello <a href="https://gitlab.rtems.org/gedare" title="Gedare Bloom" class="gfm gfm-project_member js-user-link" data-user="8" data-original="@gedare" data-container="body" data-placement="top" data-reference-type="user" style="color: #284779; background-color: #cbe2f9; border-radius: .25rem; margin-top: 0; padding: 0 2px;">@gedare</a> <a href="https://gitlab.rtems.org/joel" title="Joel Sherrill" class="gfm gfm-project_member js-user-link" data-user="7" data-original="@joel" data-container="body" data-placement="top" data-reference-type="user" style="color: #284779; background-color: #cbe2f9; border-radius: .25rem; padding: 0 2px;">@joel</a> ,</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">After studying the relevant code files and understanding the present priority bucket + bitmap implementation logic in the schedular,</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">I've created a draft MR (<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/merge_requests/1164" title="draft: Add POSIX msgq priority bucket + bitmap implementation" class="gfm gfm-merge_request" data-original="!1164" data-link="true" data-link-reference="true" data-merge-request="2455" data-project="26" data-project-path="rtems/rtos/rtems" data-iid="1164" data-container="body" data-placement="top" data-reference-type="merge_request" style="margin-top: 0;">!1164</a>) for POSIX priority message queue insertion/deletion algorithm optimization based on the discussions (<a href="https://users.rtems.org/t/gsoc-26-lower-message-priority-range-optimization/496" rel="nofollow noreferrer noopener" target="_blank">thread</a>) and findings.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">Explanation of the draft design and Implementation:</p>
<ul dir="auto" style="text-align: initial; list-style-type: disc; margin: 0 0 1rem; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">In <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">coremsg.h</code> which consists of message queue main internal structure ,
<ul style="list-style-type: circle; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">new addn :</strong> It extends <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">posix_priority</code> pointer , which makes the queue to optionally hold optimization state and NULL means fallback to legacy path</li>
</ul>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">In <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">coremsgimpl.h</code> which consists of the prototype of internal implementation
<ul style="list-style-type: circle; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">new addn :</strong>
<ul style="list-style-type: square; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<p style="color: #3a383f; margin: 0 0 1rem;"><code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">CORE_message_queue_Posix_priority_context</code> structure:</p>
<p style="color: #3a383f; margin: 0 0 1rem;">- bitmap</p>
<p style="color: #3a383f; margin: 0 0 1rem;">- per-priority bitmap info</p>
<p style="color: #3a383f; margin: 0 0 1rem;">- per-priority chain buckets</p>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<p style="color: #3a383f; margin: 0 0 1rem;">declaration for <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">_CORE_message_queue_Enable_posix_priority_buckets() </code></p>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<p style="color: #3a383f; margin: 0 0 1rem;">fast path in pending-message retrieval using bitmap.</p>
</li>
</ul>
</li>
</ul>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">In <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">mqopen.c</code> which consists of POSIX specific create/open logic
<ul style="list-style-type: circle; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">new addn</strong> : calling the enable function for priority bucket+bitmap</li>
</ul>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">In <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">coremsg.c</code> which consists of logic related to queue initialization and setup
<ul style="list-style-type: circle; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">new addn</strong> : implementation of the enabling function</li>
</ul>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">In <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">coremsgflush.c</code> which consists of the logic to clear all the pending messages
<ul style="list-style-type: circle; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">new addn</strong> : flush helper for priority bucket and bitmap reset</li>
</ul>
</li>
<li style="line-height: 1.6em; margin-left: 25px; padding-left: 3px;">in <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">coremsginsert.c</code> which consists of the actual O(n) algorithm , for the insertion of priority messages
<ul style="list-style-type: circle; margin: 0; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">new addn</strong> : append to corresponding bucket and set bitmap bit</li>
</ul>
</li>
</ul>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">With this I've also created a small draft benchmark for comparing the before and after optimization paths MR (<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/merge_requests/1151" title="draft: microbenchmark to compare the before and after optimization of posix priority message insertion" class="gfm gfm-merge_request" data-original="!1151" data-link="false" data-link-reference="false" data-merge-request="2415" data-project="26" data-project-path="rtems/rtos/rtems" data-iid="1151" data-container="body" data-placement="top" data-reference-type="merge_request" style="margin-top: 0;">!1151</a>)</p>
<ul dir="auto" style="text-align: initial; list-style-type: disc; margin: 0 0 1rem; padding: 0;">
<li style="margin-top: 0; line-height: 1.6em; margin-left: 25px; padding-left: 3px;">
<strong style="font-weight: 600; margin-top: 0;">Logic:</strong> Inserting same priority messages and filling the message queue to its limit, a receiver thread is called and made the queue to get free by exactly one space, then a sender is called to insert the message with same priority which is already present in the queue (to make sure that it traverses to the end of the queue) using <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">rtems_counter_ticks</code> and <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; white-space: pre-wrap; overflow-wrap: break-word; word-break: keep-all; padding: 0.125rem 0.25rem;">rtems_counter_read()</code>.</li>
</ul>
<p dir="auto" style="color: #3a383f; margin: 0;" align="initial">I would be grateful for any feedback or suggestions on the design and implementation.</p>
</div>
</div>
<div class="footer" style="margin-top: 10px;">
<p style="font-size: small; color: #626168;">
—
<br>
<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/5247#note_147026">View it on GitLab</a>.
<br>
You're receiving this email because of your account on <a target="_blank" rel="noopener noreferrer" href="https://gitlab.rtems.org">gitlab.rtems.org</a>. <a href="https://gitlab.rtems.org/-/sent_notifications/2-3qykc8vmo0ql4sbwgg2jvhr64/unsubscribe" target="_blank" rel="noopener noreferrer">Unsubscribe</a> from this thread · <a href="https://gitlab.rtems.org/-/profile/notifications" target="_blank" rel="noopener noreferrer" class="mng-notif-link">Manage all notifications</a> · <a href="https://gitlab.rtems.org/help" target="_blank" rel="noopener noreferrer" class="help-link">Help</a>
<span style="color: transparent; font-size: 0; display: none; overflow: hidden; opacity: 0; width: 0; height: 0; max-width: 0; max-height: 0;">
Notification message regarding https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/5247#note_147026 at 1774472168
</span>
<script type="application/ld+json">{"@context":"http://schema.org","@type":"EmailMessage","action":{"@type":"ViewAction","name":"View Issue","url":"https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/5247#note_147026"}}</script>
</p>
</div>
</body>
</html>