Critical sections
When a resource (static variable) is shared between two, or more, tasks that run at different priorities some form of mutual exclusion is required to access the memory in a data race free manner. In RTFM we use priority-based critical sections to guarantee mutual exclusion (see the Immediate Priority Ceiling Protocol).
The critical section consists of temporarily raising the dynamic priority of the task. While a task is within this critical section all the other tasks that may request the resource are not allowed to start.
How high must the dynamic priority be to ensure mutual exclusion on a particular resource? The ceiling analysis is in charge of answering that question and will be discussed in the next section. This section will focus on the implementation of the critical section.
Resource proxy
For simplicity, let's look at a resource shared by two tasks that run at
different priorities. Clearly one of the task can preempt the other; to prevent
a data race the lower priority task must use a critical section when it needs
to modify the shared memory. On the other hand, the higher priority task can
directly modify the shared memory because it can't be preempted by the lower
priority task. To enforce the use of a critical section on the lower priority
task we give it a resource proxy, whereas we give a mutable reference
(&mut-
) to the higher priority task.
The example below shows the different types handed out to each task:
# #![allow(unused_variables)] #fn main() { #[rtfm::app(device = ..)] const APP: () = { static mut X: u64 = 0; #[interrupt(binds = UART0, priority = 1, resources = [X])] fn foo(c: foo::Context) { // resource proxy let mut x: resources::X = c.resources.X; x.lock(|x: &mut u64| { // critical section *x += 1 }); } #[interrupt(binds = UART1, priority = 2, resources = [X])] fn bar(c: foo::Context) { let mut x: &mut u64 = c.resources.X; *x += 1; } // .. }; #}
Now let's see how these types are created by the framework.
# #![allow(unused_variables)] #fn main() { fn foo(c: foo::Context) { // .. user code .. } fn bar(c: bar::Context) { // .. user code .. } pub mod resources { pub struct X { // .. } } pub mod foo { pub struct Resources { pub X: resources::X, } pub struct Context { pub resources: Resources, // .. } } pub mod bar { pub struct Resources<'a> { pub X: rtfm::Exclusive<'a, u64>, // newtype over `&'a mut u64` } pub struct Context { pub resources: Resources, // .. } } const APP: () = { static mut X: u64 = 0; impl rtfm::Mutex for resources::X { type T = u64; fn lock<R>(&mut self, f: impl FnOnce(&mut u64) -> R) -> R { // we'll check this in detail later } } #[no_mangle] unsafe fn UART0() { foo(foo::Context { resources: foo::Resources { X: resources::X::new(/* .. */), }, // .. }) } #[no_mangle] unsafe fn UART1() { bar(bar::Context { resources: bar::Resources { X: rtfm::Exclusive(&mut X), }, // .. }) } }; #}
lock
Let's now zoom into the critical section itself. In this example, we have to
raise the dynamic priority to at least 2
to prevent a data race. On the
Cortex-M architecture the dynamic priority can be changed by writing to the
BASEPRI
register.
The semantics of the BASEPRI
register are as follows:
- Writing a value of
0
toBASEPRI
disables its functionality. - Writing a non-zero value to
BASEPRI
changes the priority level required for interrupt preemption. However, this only has an effect when the written value is lower than the priority level of current execution context, but note that a lower hardware priority level means higher logical priority
Thus the dynamic priority at any point in time can be computed as
# #![allow(unused_variables)] #fn main() { dynamic_priority = max(hw2logical(BASEPRI), hw2logical(static_priority)) #}
Where static_priority
is the priority programmed in the NVIC for the current
interrupt, or a logical 0
when the current context is idle
.
In this particular example we could implement the critical section as follows:
NOTE: this is a simplified implementation
# #![allow(unused_variables)] #fn main() { impl rtfm::Mutex for resources::X { type T = u64; fn lock<R, F>(&mut self, f: F) -> R where F: FnOnce(&mut u64) -> R, { unsafe { // start of critical section: raise dynamic priority to `2` asm!("msr BASEPRI, 192" : : : "memory" : "volatile"); // run user code within the critical section let r = f(&mut implementation_defined_name_for_X); // end of critical section: restore dynamic priority to its static value (`1`) asm!("msr BASEPRI, 0" : : : "memory" : "volatile"); r } } } #}
Here it's important to use the "memory"
clobber in the asm!
block. It
prevents the compiler from reordering memory operations across it. This is
important because accessing the variable X
outside the critical section would
result in a data race.
It's important to note that the signature of the lock
method prevents nesting
calls to it. This is required for memory safety, as nested calls would produce
multiple mutable references (&mut-
) to X
breaking Rust aliasing rules. See
below:
# #![allow(unused_variables)] #fn main() { #[interrupt(binds = UART0, priority = 1, resources = [X])] fn foo(c: foo::Context) { // resource proxy let mut res: resources::X = c.resources.X; res.lock(|x: &mut u64| { res.lock(|alias: &mut u64| { //~^ error: `res` has already been mutably borrowed // .. }); }); } #}
Nesting
Nesting calls to lock
on the same resource must be rejected by the compiler
for memory safety but nesting lock
calls on different resources is a valid
operation. In that case we want to make sure that nesting critical sections
never results in lowering the dynamic priority, as that would be unsound, and we
also want to optimize the number of writes to the BASEPRI
register and
compiler fences. To that end we'll track the dynamic priority of the task using
a stack variable and use that to decide whether to write to BASEPRI
or not. In
practice, the stack variable will be optimized away by the compiler but it still
provides extra information to the compiler.
Consider this program:
# #![allow(unused_variables)] #fn main() { #[rtfm::app(device = ..)] const APP: () = { static mut X: u64 = 0; static mut Y: u64 = 0; #[init] fn init() { rtfm::pend(Interrupt::UART0); } #[interrupt(binds = UART0, priority = 1, resources = [X, Y])] fn foo(c: foo::Context) { let mut x = c.resources.X; let mut y = c.resources.Y; y.lock(|y| { *y += 1; *x.lock(|x| { x += 1; }); *y += 1; }); // mid-point x.lock(|x| { *x += 1; y.lock(|y| { *y += 1; }); *x += 1; }) } #[interrupt(binds = UART1, priority = 2, resources = [X])] fn bar(c: foo::Context) { // .. } #[interrupt(binds = UART2, priority = 3, resources = [Y])] fn baz(c: foo::Context) { // .. } // .. }; #}
The code generated by the framework looks like this:
# #![allow(unused_variables)] #fn main() { // omitted: user code pub mod resources { pub struct X<'a> { priority: &'a Cell<u8>, } impl<'a> X<'a> { pub unsafe fn new(priority: &'a Cell<u8>) -> Self { X { priority } } pub unsafe fn priority(&self) -> &Cell<u8> { self.priority } } // repeat for `Y` } pub mod foo { pub struct Context { pub resources: Resources, // .. } pub struct Resources<'a> { pub X: resources::X<'a>, pub Y: resources::Y<'a>, } } const APP: () = { #[no_mangle] unsafe fn UART0() { // the static priority of this interrupt (as specified by the user) const PRIORITY: u8 = 1; // take a snashot of the BASEPRI let initial: u8; asm!("mrs $0, BASEPRI" : "=r"(initial) : : : "volatile"); let priority = Cell::new(PRIORITY); foo(foo::Context { resources: foo::Resources::new(&priority), // .. }); // roll back the BASEPRI to the snapshot value we took before asm!("msr BASEPRI, $0" : : "r"(initial) : : "volatile"); } // similarly for `UART1` impl<'a> rtfm::Mutex for resources::X<'a> { type T = u64; fn lock<R>(&mut self, f: impl FnOnce(&mut u64) -> R) -> R { unsafe { // the priority ceiling of this resource const CEILING: u8 = 2; let current = self.priority().get(); if current < CEILING { // raise dynamic priority self.priority().set(CEILING); let hw = logical2hw(CEILING); asm!("msr BASEPRI, $0" : : "r"(hw) : "memory" : "volatile"); let r = f(&mut X); // restore dynamic priority let hw = logical2hw(current); asm!("msr BASEPRI, $0" : : "r"(hw) : "memory" : "volatile"); self.priority().set(current); r } else { // dynamic priority is high enough f(&mut X) } } } } // repeat for `Y` }; #}
At the end the compiler will optimize the function foo
into something like
this:
# #![allow(unused_variables)] #fn main() { fn foo(c: foo::Context) { // NOTE: BASEPRI contains the value `0` (its reset value) at this point // raise dynamic priority to `3` unsafe { asm!("msr BASEPRI, 160" : : : "memory" : "volatile") } // the two operations on `Y` are merged into one Y += 2; // BASEPRI is not modified to access `X` because the dynamic priority is high enough X += 1; // lower (restore) the dynamic priority to `1` unsafe { asm!("msr BASEPRI, 224" : : : "memory" : "volatile") } // mid-point // raise dynamic priority to `2` unsafe { asm!("msr BASEPRI, 192" : : : "memory" : "volatile") } X += 1; // raise dynamic priority to `3` unsafe { asm!("msr BASEPRI, 160" : : : "memory" : "volatile") } Y += 1; // lower (restore) the dynamic priority to `2` unsafe { asm!("msr BASEPRI, 192" : : : "memory" : "volatile") } // NOTE: it would be sound to merge this operation on X with the previous one but // compiler fences are coarse grained and prevent such optimization X += 1; // lower (restore) the dynamic priority to `1` unsafe { asm!("msr BASEPRI, 224" : : : "memory" : "volatile") } // NOTE: BASEPRI contains the value `224` at this point // the UART0 handler will restore the value to `0` before returning } #}
The BASEPRI invariant
An invariant that the RTFM framework has to preserve is that the value of the BASEPRI at the start of an interrupt handler must be the same value it has when the interrupt handler returns. BASEPRI may change during the execution of the interrupt handler but running an interrupt handler from start to finish should not result in an observable change of BASEPRI.
This invariant needs to be preserved to avoid raising the dynamic priority of a handler through preemption. This is best observed in the following example:
# #![allow(unused_variables)] #fn main() { #[rtfm::app(device = ..)] const APP: () = { static mut X: u64 = 0; #[init] fn init() { // `foo` will run right after `init` returns rtfm::pend(Interrupt::UART0); } #[task(binds = UART0, priority = 1)] fn foo() { // BASEPRI is `0` at this point; the dynamic priority is currently `1` // `bar` will preempt `foo` at this point rtfm::pend(Interrupt::UART1); // BASEPRI is `192` at this point (due to a bug); the dynamic priority is now `2` // this function returns to `idle` } #[task(binds = UART1, priority = 2, resources = [X])] fn bar() { // BASEPRI is `0` (dynamic priority = 2) X.lock(|x| { // BASEPRI is raised to `160` (dynamic priority = 3) // .. }); // BASEPRI is restored to `192` (dynamic priority = 2) } #[idle] fn idle() -> ! { // BASEPRI is `192` (due to a bug); dynamic priority = 2 // this has no effect due to the BASEPRI value // the task `foo` will never be executed again rtfm::pend(Interrupt::UART0); loop { // .. } } #[task(binds = UART2, priority = 3, resources = [X])] fn baz() { // .. } }; #}
IMPORTANT: let's say we forget to roll back BASEPRI
in UART1
-- this would
be a bug in the RTFM code generator.
# #![allow(unused_variables)] #fn main() { // code generated by RTFM const APP: () = { // .. #[no_mangle] unsafe fn UART1() { // the static priority of this interrupt (as specified by the user) const PRIORITY: u8 = 2; // take a snashot of the BASEPRI let initial: u8; asm!("mrs $0, BASEPRI" : "=r"(initial) : : : "volatile"); let priority = Cell::new(PRIORITY); bar(bar::Context { resources: bar::Resources::new(&priority), // .. }); // BUG: FORGOT to roll back the BASEPRI to the snapshot value we took before // asm!("msr BASEPRI, $0" : : "r"(initial) : : "volatile"); } }; #}
The consequence is that idle
will run at a dynamic priority of 2
and in fact
the system will never again run at a dynamic priority lower than 2
. This
doesn't compromise the memory safety of the program but affects task scheduling:
in this particular case tasks with a priority of 1
will never get a chance to
run.