feat: selection policy in UART virtualizer by frihetselsker · Pull Request #4802 · tock/tock

frihetselsker · 2026-04-22T09:22:56Z

Pull Request Overview

This pull request fixes the fairness problem of virtual devices. So far it only implements it for the UART Mux, but if approved, the same fix will be easily implemented for the rest of the affected Muxes.

The Fairness Problem

When searching for the next operation, multiplexers (except the Alarm) will always iterate the devices list from beginning to end. This means that if one device always has a job and it was inserted earlier, it will always be picked.

The following examples illustrates the problem for the UART Mux. If debug!() is called frequently (for example in the UartMux), the DebugConsole has a monopoly over the UART Multiplexer, as it will be the only devices chosen to print.

Solution

We introduce the SelectionPolicy trait that provides Muxes with the device selection logic. It is a generic type and should not add any overhead, neither in speed, neither in code space.

We define two policies:

InsertionFirstPolicy that behaves like Muxes used to behave so far, it iterates the list from the beginning to the end. This provides backward compatibility.
RoundRobinPolicy that iterates the devices list in a round robin manner. Using this policy with the previous debug! examples allows all device to print.

This solution offers a structural change that gives users the freedom to choose the policy they want. By default, the UART Mux uses the InsertionFirstPolicy and there are no changes required in the code.

Users will now able to implement their own selection policies for the UART Mux.

Testing Strategy

This pull request was tested by using a custom kernel of qemu_rv32_virt with UART peripheral, and three equivalent applications that try to use printf() simultaneously.

TODO or Help Wanted

Feedback

Documentation Updated

Updated the relevant files in /docs, or no updates are required.

We are unsure of the proper placement of the documentation in the README file. Help is needed here as well.

Formatting

Ran make prepush.

AI Use

The PR description details my use of AI in the production of the
code in this PR, if any, and I have manually checked and
personally certify the entire contents of this PR.

No AI was used for this PR.

lschuermann · 2026-04-22T14:42:04Z

Thanks @frihetselsker, priority and queue managers in virtualizers is not something we've considered much so far. Before we dive into the code, may I ask to do revisit the "AI Use" section of the PR comment and, if applicable, detail whether and how you used Gen-AI to help with this PR? It's poorly worded right now, but we require checking this box even if you did not use any of these tools currently (which #4792 proposes to change).

bradjc · 2026-04-22T15:14:36Z

This is a long standing issue, and it's great you are looking at it.

I do wonder, however, why a board would want the uart mux to prioritize apps in the order they are in the processes array (e.g., InsertionFirst) rather than round robin. Is InsertionFirst just for backwards compatibility and to not change current behavior, while still allowing RoundRobin? Or is there a specific use case you have in mind for wanting to use InsertionFirst or both for different virtualizers?

I guess what I'm asking, is would it be better to just have a round robin iterator tool and just switch all capsules to use that rather than apps.each directly.

alexandruradovici · 2026-04-22T15:28:23Z

This is a long standing issue, and it's great you are looking at it.

I do wonder, however, why a board would want the uart mux to prioritize apps in the order they are in the processes array (e.g., InsertionFirst) rather than round robin. Is InsertionFirst just for backwards compatibility and to not change current behavior, while still allowing RoundRobin? Or is there a specific use case you have in mind for wanting to use InsertionFirst or both for different virtualizers?

I guess what I'm asking, is would it be better to just have a round robin iterator tool and just switch all capsules to use that rather than apps.each directly.

This is not related to applications, but to the mux that serves capsules. For the UART specifically, the console capsule handles the applications order, the mux handles several capsules that require the UART.

InsertionFirst is only for backward compatibility, as some downstream users may rely on this, and refers to the order in which the VirtualUart devices were added to the mux. Each capsule usually has one VirtualUart, applications all share the console's VirtualUart

bradjc · 2026-04-22T15:40:55Z

This is not related to applications, but to the mux that serves capsules. For the UART specifically, the console capsule handles the applications order, the mux handles several capsules that require the UART.

Oh, right. A board could strategically assign its virtual devices in the mux, I suppose, a little bit more effectively than processes in the process array.

InsertionFirst is only for backward compatibility, as some downstream users may rely on this, and refers to the order in which the VirtualUart devices were added to the mux. Each capsule usually has one VirtualUart, applications all share the console's VirtualUart

Personally, I don't think we ever guaranteed this behavior and I think virtualized devices should not have any guarantee about their priority. So I'm find changing the behavior.

alexandruradovici · 2026-04-22T15:47:48Z

Personally, I don't think we ever guaranteed this behavior and I think virtualized devices should not have any guarantee about their priority. So I'm find changing the behavior.

Even if we delete the InsertionFirst and make RoundRobin the default, I think keeping the idea that users can configure the mux selection behaviour is valuable.

bradjc · 2026-04-22T17:07:57Z

Personally, I don't think we ever guaranteed this behavior and I think virtualized devices should not have any guarantee about their priority. So I'm find changing the behavior.

Even if we delete the InsertionFirst and make RoundRobin the default, I think keeping the idea that users can configure the mux selection behaviour is valuable.

Can you elaborate on that? If whoever created the first mux had implemented a generic round robin iterator that all other muxes copied, I'm dubious that anyone would now push to have the option to prioritize the first thing added to the mux.

frihetselsker · 2026-04-22T19:31:00Z

Thanks @frihetselsker, priority and queue managers in virtualizers is not something we've considered much so far. Before we dive into the code, may I ask to do revisit the "AI Use" section of the PR comment and, if applicable, detail whether and how you used Gen-AI to help with this PR? It's poorly worded right now, but we require checking this box even if you did not use any of these tools currently (which #4792 proposes to change).

Sorry, I didn't check because I wasn't sure what to do since I hadn't used AI to write this code.

alexandruradovici · 2026-04-27T09:27:39Z

Personally, I don't think we ever guaranteed this behavior and I think virtualized devices should not have any guarantee about their priority. So I'm find changing the behavior.

Even if we delete the InsertionFirst and make RoundRobin the default, I think keeping the idea that users can configure the mux selection behaviour is valuable.

Can you elaborate on that? If whoever created the first mux had implemented a generic round robin iterator that all other muxes copied, I'm dubious that anyone would now push to have the option to prioritize the first thing added to the mux.

The issue is more generic than having the first thing added to the mux. The idea is to allow downstream users to control the way in which the muxes select the next device. For instance, we may have capsules controlling hardware that have different priorities based on the state in which a device is. For a car, they would have to behave differently when the car is in PARK than when the car is in DRIVE. Adding the SelectionPolicy trait allows this.

Whether we should use the RoundRobin as the default implementation is another discussion. If breaking downstream behaviour is not a problem, as this was never documented, then I think we can drop the InsertionFirst.

bradjc · 2026-04-27T15:30:47Z

The issue is more generic than having the first thing added to the mux. The idea is to allow downstream users to control the way in which the muxes select the next device. For instance, we may have capsules controlling hardware that have different priorities based on the state in which a device is. For a car, they would have to behave differently when the car is in PARK than when the car is in DRIVE. Adding the SelectionPolicy trait allows this.

I'm coming around to the idea of having the capability to implement dynamic list selection policies as useful. I think we should think through the trait.

bradjc

We want to move forward with this approach, and we can just do the switch to round robin.

Hopefully board main.rs files don't need to change.

We do need to fix the CI test.

bradjc · 2026-05-13T19:45:15Z

+/// Default policy which selects the first ready device starting from the beginning of the list.
+pub struct InsertionFirstPolicy;
+
+impl<I> SelectionPolicy<I> for InsertionFirstPolicy {
+    fn select<It>(&self, mut it: It, ready: impl Fn(&I) -> bool) -> Option<I>
+    where
+        It: Iterator<Item = I>,
+    {
+        it.find(|node| ready(node))
+    }
+}


Remove this.

bradjc · 2026-05-13T19:45:31Z

+impl Default for RoundRobinPolicy {
+    fn default() -> Self {
+        Self {
+            last_access_position: Cell::new(0),
+        }
+    }
+}


Shouldn't need this.

bradjc · 2026-05-13T19:46:08Z

 pub const RX_BUF_LEN: usize = 64;

-pub struct MuxUart<'a> {
+pub struct MuxUart<'a, P: SelectionPolicy<&'a UartDevice<'a, P>> = InsertionFirstPolicy> {


Suggested change

pub struct MuxUart<'a, P: SelectionPolicy<&'a UartDevice<'a, P>> = InsertionFirstPolicy> {

pub struct MuxUart<'a, P: SelectionPolicy<&'a UartDevice<'a, P>>> {

bradjc · 2026-05-13T19:46:30Z

+    /// Create a new Mux with the [`InsertionFirstPolicy`] selection policy.
+    pub fn new(
+        uart: &'a dyn uart::Uart<'a>,
+        buffer: &'static mut [u8],
+        speed: u32,
+    ) -> MuxUart<'a, InsertionFirstPolicy> {
+        MuxUart {
+            uart,


Suggested change

/// Create a new Mux with the [`InsertionFirstPolicy`] selection policy.

pub fn new(

uart: &'a dyn uart::Uart<'a>,

buffer: &'static mut [u8],

speed: u32,

) -> MuxUart<'a, InsertionFirstPolicy> {

MuxUart {

uart,

pub fn new(

uart: &'a dyn uart::Uart<'a>,

buffer: &'static mut [u8],

speed: u32,

) -> Self {

Self {

uart,

bradjc · 2026-05-13T19:46:55Z

+    ///
+    /// For the default implementation, please refer to [`MuxUart::new`] function
+    /// which uses [`InsertionFirstPolicy`] selection policy.
+    pub fn new_with_policy(


Don't need.

bradjc · 2026-05-13T19:48:13Z

+            $P
+        )
+    }};
+    // By default, if no selection policy is provided we will use the `InsertionFirstPolicy`.


Default to round robin.

github-actions Bot added kernel component labels Apr 22, 2026

frihetselsker force-pushed the virt/selection_policy branch from 33269b3 to 2da4851 Compare April 22, 2026 10:13

github-actions Bot assigned jrvanwhy Apr 23, 2026

bradjc reviewed Apr 27, 2026

View reviewed changes

Comment thread capsules/core/src/virtualizers/selection_policy.rs

feat: selection policy in UART virtualizer

1a37768

frihetselsker force-pushed the virt/selection_policy branch from 2da4851 to 1a37768 Compare April 30, 2026 07:42

frihetselsker mentioned this pull request Apr 30, 2026

feat: round robin selection in virtualizers #4818

Open

3 tasks

bradjc reviewed May 13, 2026

View reviewed changes

bradjc mentioned this pull request Jun 9, 2026

Update to #4802: Add RoundRobinPolicy selection policy #4868

Open

3 tasks

	pub struct MuxUart<'a, P: SelectionPolicy<&'a UartDevice<'a, P>> = InsertionFirstPolicy> {
	pub struct MuxUart<'a, P: SelectionPolicy<&'a UartDevice<'a, P>>> {

Uh oh!

Conversation

frihetselsker commented Apr 22, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Overview

The Fairness Problem

Solution

Testing Strategy

TODO or Help Wanted

Documentation Updated

Formatting

AI Use

Uh oh!

lschuermann commented Apr 22, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bradjc commented Apr 22, 2026

Uh oh!

alexandruradovici commented Apr 22, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bradjc commented Apr 22, 2026

Uh oh!

alexandruradovici commented Apr 22, 2026

Uh oh!

bradjc commented Apr 22, 2026

Uh oh!

frihetselsker commented Apr 22, 2026

Uh oh!

alexandruradovici commented Apr 27, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

bradjc commented Apr 27, 2026

Uh oh!

bradjc left a comment

Choose a reason for hiding this comment

Uh oh!

bradjc May 13, 2026

Choose a reason for hiding this comment

Uh oh!

bradjc May 13, 2026

Choose a reason for hiding this comment

Uh oh!

bradjc May 13, 2026

Choose a reason for hiding this comment

Uh oh!

bradjc May 13, 2026

Choose a reason for hiding this comment

Uh oh!

bradjc May 13, 2026

Choose a reason for hiding this comment

Uh oh!

bradjc May 13, 2026

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

frihetselsker commented Apr 22, 2026 •

edited

Loading

lschuermann commented Apr 22, 2026 •

edited

Loading

alexandruradovici commented Apr 22, 2026 •

edited

Loading

alexandruradovici commented Apr 27, 2026 •

edited

Loading