Mutex can deadlock when used with multiple priority tasks

[pattop]

Below is a test case demonstrating the issue.

I think what's happening is that the two high priority tasks are fighting over the mutex, preventing the low priority task from making forward progress so that it can release the mutex.

#![no_std]
#![no_main]
#![feature(type_alias_impl_trait)]

use defmt_rtt as _;
use embassy_stm32::{
    executor::Executor, executor::InterruptExecutor, interrupt, interrupt::InterruptExt, time,
};
use embassy_sync::blocking_mutex::raw::CriticalSectionRawMutex;
use embassy_sync::mutex::Mutex;
use embassy_time::{Duration, Timer};
use static_cell::StaticCell;

static MUTEX: Mutex<CriticalSectionRawMutex, u32> = Mutex::new(0);

#[cortex_m_rt::entry]
fn main() -> ! {
    /* clocks */
    let mut cfg = embassy_stm32::Config::default();
    cfg.rcc.hse = Some(time::mhz(8));
    cfg.rcc.sys_ck = Some(time::mhz(180));
    embassy_stm32::init(cfg);

    /* enable flash cache & prefetching */
    unsafe {
        embassy_stm32::pac::FLASH.acr().modify(|w| {
            w.set_dcen(true);
            w.set_icen(true);
            w.set_prften(true);
        });
    }

    /* high priority */
    let irq = interrupt::take!(UART4);
    irq.set_priority(interrupt::Priority::P14);
    static EXECUTOR_HIGH: StaticCell<InterruptExecutor<interrupt::UART4>> = StaticCell::new();
    let executor = EXECUTOR_HIGH.init(InterruptExecutor::new(irq));
    let spawner = executor.start();
    defmt::unwrap!(spawner.spawn(high_task(1)));
    defmt::unwrap!(spawner.spawn(high_task(2)));

    /* low priority */
    static EXECUTOR_LOW: StaticCell<Executor> = StaticCell::new();
    let executor = EXECUTOR_LOW.init(Executor::new());
    executor.run(|spawner| {
        defmt::unwrap!(spawner.spawn(low_task()));
    });
}

#[embassy_executor::task]
async fn low_task() {
    loop {
        defmt::println!("low priority task locking mutex");
        let mut m = MUTEX.lock().await;
        defmt::println!("low priority task got mutex");
	for i in 0..10 {
		cortex_m::asm::delay(10000000); // ~100 millisecond
		defmt::println!("low priority task busy {}", i);
	}
	*m += 1;
        defmt::println!("low priority task releasing mutex");
    }
}

#[embassy_executor::task(pool_size=2)]
async fn high_task(i: usize) {
    defmt::println!("high priority task {} waiting", i);
    Timer::after(Duration::from_millis(500)).await;
    loop {
        defmt::println!("high priority task {} locking mutex", i);
        let mut m = MUTEX.lock().await;
        defmt::println!("high priority task {} got mutex", i);
        Timer::after(Duration::from_millis(500)).await;
	*m += 1;
        defmt::println!("high priority task {} releasing mutex", i);
    }
}

#[panic_handler]
fn panic(panic: &core::panic::PanicInfo) -> ! {
    defmt::error!("{}", defmt::Display2Format(panic));
    cortex_m::asm::udf();
}

[lulf]

I think the problem here is that the high priority task, once dropping the mutex at the end of the loop, will re-acquire it before the low-pri task has a chance of acquiring it. If you look at the implementation, you can see that a lock() will ignore an existing waker, so this is a known limitation (though documentation should be added) to keep the mutex small I think.

We can improve the existing mutex to handle this, though maybe not without a cost. For now, you can use the mutex from futures-intrusive: https://docs.rs/futures-intrusive/0.5.0/futures_intrusive/sync/struct.GenericMutex.html which you can configure to be fair, and that should work for your use case.

[pattop]

Thanks for the link to futures intrusive, I'll have a look.

I just realised that I didn't include the output of the test program.

What's happening in this test is that the low priority task acquires the mutex while the high priority tasks are sleeping, the high priority tasks then wake up and try to acquire the mutex while the low priority task is holding it and performing some busy processing. Because the high priority tasks keep kicking each other out of the wait, the low priority task can never run again leading to the deadlock described.

[lulf]

Ah, I missed that there were two high prio tasks. The root cause is the same though I believe: a task will ignore that there is a waiter for the mutex. To make it fair and not deadlock, I think we need an ordered list/queue of wakers in the mutex.

[pattop]

For completeness, here's the output of the test case above:

0.000061 high priority task 1 waiting
0.000211 high priority task 2 waiting
0.000367 low priority task locking mutex
0.000438 low priority task got mutex
0.083868 low priority task busy 0
0.167346 low priority task busy 1
0.250816 low priority task busy 2
0.334302 low priority task busy 3
0.417771 low priority task busy 4
0.500193 high priority task 1 locking mutex
0.500341 high priority task 2 locking mutex

[xgroleau]

Has there be any development on this issue? From what I understand, an intrusive queue of waker or a similar solution would need to be implemented in the embassy mutex?

If we know the direction we want to go I might try to implement it after the holidays.

[lulf]

Not really, feel free to pick it up. Note that you can use the futures-intrusive mutex as a workaround.