Potential priority inversion in closed receive protocols

Background/problem

We have a (known) priority inversion opportunity in the OS. It has to do with our use of closed receive to implement mutual exclusion, and is most easily demonstrated by considering the SPI task:

1. Unimportant task contacts SPI driver and requests to lock it. It succeeds.
2. Important task tries to contact SPI driver, is queued. Now we have important work waiting on unimportant work, which isn't great but is hard to avoid.
3. Medium-important task loses its mind and doesn't yield CPU to the unimportant task. Now the medium-important task is able to prevent the important task from making progress, which was not the design intent (and is also bad).

I knew this was going to be a risk, so some core features of Hubris are designed to make it relatively easy to mitigate -- but we ain't done it yet, and we prolly oughtta. Hence this bug report.

FWIW, we haven't seen any bugs caused by this in practice, likely because we don't use mutual exclusion patterns very much. To make this happen, I'm pretty sure you have to be using "closed receive." Closed receive is the sys_recv mode that only listens for a single task, instead of the highest priority queued sender. It's how we implement mutual exclusion on the SPI driver.

Proposed fix, in the abstract

I suspect the easiest way to fix this would be by using Priority Ceiling Protocol or a derivative of it. Priority Inheritance is a popular way to fix this in realtime operating systems, but ironically priority inheritance has some features that make it hard to implement in constant time: to make unblocking an arbitrary waiter cheap, you need complex minheap structures (and thus dynamic allocation); otherwise it winds up approaching linear. While we're not as aggressively realtime as some systems, I'd sure like to avoid building load-sensitive operations into the kernel, since we've largely avoided it until now.

An application of priority ceiling protocol for the SPI mutual exclusion case would change the original scenario as follows:

1. Unimportant task contacts SPI driver and requests to lock it. It succeeds.
2. Important task tries to contact SPI driver, is queued. Now we have important work waiting on unimportant work, which isn't great but is hard to avoid.
3. At or before this point, the priority of the unimportant task is temporarily boosted to be at least as high as all clients of the SPI task. (Variations described below.)
4. Medium-important task does not have an opportunity to be scheduled because of the priority boost and can no longer interfere.
5. Previously-unimportant-but-now-boosted task finishes its work and yields to the important task.

PCP comes in several variations, which I alluded to above. There's the axis of "when to boost:"

• You can boost the priority immediately when locking the resource, i.e. the unimportant task would be boosted as soon as it gets the reply from lock. This is simple and easy to reason about, but it can also starve intermediate-priority tasks that have nothing to do with the resource.
• You can wait to boost the priority until at least one other task is contending for the resource. This reduces the impact of priority boosting in the (presumably more common) uncontended case. Note that a key difference of PCP over priority inheritance is that, even if you wait for a competitor before boosting, you still boost the priority as high as it needs to go.

And then there's the axis of "how to boost:"

• If you can identify all potential contenders for a resource, you only need to boost to the highest priority among them. Much like waiting to boost until the resource is actually contended, this reduces the system overhead of PCP.
• If you can't, or if you want to be really sure of something, you can boost the priority to that of the resource itself. (Since we require IPCs to always go "uphill" in terms of priority, in our case it'd be the priority of the resource, minus one.)

Notes on potential implementation and open design questions

With the exception of certain dynamic tasks used for debugging, like hiffy's generic send support and udprpc, we can identify all potential clients of a service at compile time. So, we have the opportunity to do a more precise priority boost. That's nice.

To do this, there's some basic implementation work to do, but also some design work. First, the implementation work: we'd need to start adjusting task priorities. This is easy because I did most of it four years ago:

• Tasks distinguish between initial priority (in ROM) and current priority (in RAM) already
• The basic data structure we use for handling task wait queues doesn't require updates if the task priorities inside it change. (Because it is really, really simple, and slower than it could be if it were more complex.)

Now, the design work:

• How do we know when to boost a task's priority? Consider the SPI lock operation -- it's a normal IPC, nothing about it indicates that it needs special handling. It's also the only operation on the SPI IPC interface that should be handled this way. (My guess is that we'll want a variation on the REPLY primitive.)
• How do we know when to stop boosting the priority? (Possibly also a variation on the REPLY primitive? But also definitely if the task should restart.)
• How do we know what priority to boost to? (As noted above, we can probably determine this at build time, but then we need to make that metadata available to whatever entity activates the boost.)
• Who keeps track of which tasks are boosted? If it's state in the server only, how do we un-boost a task if the server restarts? If it's state in the kernel, how do we keep it in sync with the server?

...and probably other questions.

No specific files or tests are named. Start by tracing closed receive, the sys_recv mode, task current-priority handling, wait queues, and the SPI lock IPC; review how a REPLY variation could carry boosting state. Done requires choosing and implementing a priority-ceiling design, including boost timing, priority selection, and cleanup across server restarts.