esp-idf: Incorrect semaphore behavior in FreeRTOS under esp-idf (IDFGH-7260)

@Dazza0

You said there is no easy way to fix this. But you are aware the bug is real and this has been reported by many people. So what make you think it’s ok to live with this bug?

@acf-bwl @AxelLin I’ve taken a look at this issue and have been able to recreate this locally on multiple releases. The issue you’re seeing is one scenario of the more general “spinlock acquire race condition” previously described in this comment.

This issue is quite difficult to explain, so I’ll provide a quick, summary here and leave the full explanations below.

• This bug essentially involves a lower priority task A on core X stealing a (queue message/mutex/semaphore) from a higher priority blocked task B on core Y. It is a result of some single-core FreeRTOS assumptions no longer being true under SMP.
• The good news is that this race condition shouldn’t be an issue in IDF applications, thus why the same queue/mutex/semaphore implementation has been used in IDF for many releases without this race condition causing a noticeable error (see explanation below).
• The bad news is that there is not easy way to fix this race condition. Any immediate fixes can either cause more undesirable scheduling behavior, or increased complexity in the queue/semaphore/mutex implementation. I’ve described some possible approaches and (why they won’t work/cost benefit).

Critical Section Race Condition

All FreeRTOS queues/semaphores/mutex read/write functions will internally use a loop. The pseudo code below illustrates the rough behavioral flow of these functions:

BaseType_t xQueueSend/Receive/SemaphoreTake(...)
{
    // Main fucntion loop
    for(;;) {
        // Race condition happens here, before we enter the critical section.
        taskENTER_CRITICAL();
        // Check for empty/full queue/semaphore/mutex
        if (not empty/full) {
            // Read/write here
        else {
            // Flow downwards to enter timeout
        }
        taskEXIT_CRITICAL();

        // Handle timeout stuff
        vTaskSuspendAll();
        prvLockQueue( pxQueue );
        if (not_timed_out) {
            // Haven't timed out yet. Yield (i.e., block) on the queue/sempahore/mutex
            prvUnlockQueue( pxQueue );
            ( void ) xTaskResumeAll();
            portYIELD_WITHIN_API();
        } else {
            prvUnlockQueue( pxQueue );
            ( void ) xTaskResumeAll();
        }
        /* Once we are here, we either:
        - Have timed out, in which case we return just return from this function
        - Have blocked from portYIELD_WITHIN_API(), then been unblocked because a message has been received/emptied. So we...
            - loop back around
            - Enter the critical section
            - Check for a message/empty space
            - Read/write our message
        */
    }
}

Note: In IDF’s SMP FreeRTOS, we replace the queue locks with a critical section, but this doesn’t affect the race condition.

From the pseudo code above, you’ll notice that after a task blocks on a queue/semaphore/mutex, it will remain blocked until it times out, or is unblocked by another task/ISR by reading/writing a message to the queue/semaphore/mutex.

For example, if a “task A” tires to read an empty queue, it will block at the point of the portYIELD_WITHIN_API() call. If another “task B” then writes to the queue, “task A” will unblock and resume execution right after the portYIELD_WITHIN_API(). You’ll notice that “task A” must then…

1. Loop back around to the top of the loop
2. Then re-enter a critical section so that the queue can be read safely.

It is at this point where the race condition can occur. If a “task C” of lower priority but running on the other core also attempts to read the queue at the same time, “task C” can beat “task A” in entering that critical section first (in SMP this means “task C” acquires the spinlock first). Thus, the following occurs:

1. “task C” of lower priority enters the critical section first (i.e., acquires the spinlock first) while "task A’ is still looping back around
2. “task C” sees that the queue has a message and reads it. Meanwhile, “task A” is still stuck trying to enter the critical section (waiting for the spinlock to be released)
3. “task C” has read a message so it doesn’t need to block. It exits the critical and simply returns from the function
4. “task A” is now able to enter the critical section, but now the queue is empty (because “task C” stole the message). “task A” follows the same flow of blocking on an empty queue.

Thus, as a result, under some narrow timing circumstances, it is possible for a lower priority “task C” to “cut in line” of the queue and get a message before a blocked higher priority “task A”.

On single-core, this race condition cannot occur because only one task (which is the highest priority task) can run at any one time. Thus, in single core, if the same “task A” is looping back around after being unblocked:

• No lower priority tasks will run because there is only one core, and the scheduler will never scheduler a lower priority task
• If a higher priority “task B” preempts “task A” while it is looping back around, and “task B” also reads the same queue, this should be fine (might be intended behavior by FreeRTOS) as “task B” is higher priority (thus is should rightfully get the message first.

Implications on SMP in IDF

This race condition isn’t an issue in most IDF applications for the following reasons:

Narrow Timing Window

This race condition requires a very specific timing window (with one core looping back around just after being unblocked, and the other core contesting the queue at the same time). Thus to get a full starvation scenario requires very careful and repeatable timing (as demonstrated in the example code you have provided).

In the vast majority of queue/semaphore/mutex use cases, a task will receive/take the queue/sempahore/mutex, and then carry out some some sort of action (either process the message, handle the event indicated by the semaphore, or access the resource protected by the mutex). These actions are usually variable time, thus making it unlikely for the race condition timing window to consistently occur.

Furthermore, timing variance introduced by timer interrupts and cache misses further makes it unlikely for a task to be consistently starved.

Priority Inversion Tolerance

Even if this race condition occasionally occurs, the usual result is that a task simply blocks until the next message (while the previous message was stolen by the lower priority task). However IDF components don’t rely on task priority for correct behavior. For example, some single core FreeRTOS applications may relay on the fact that a task is the highest priority task, thus has exclusive access to a particular resource. But this assumption is never made in IDF (because a task on the other core is running concurrently). Thus (sequential order/exclusive access) in IDF components is always guarded by using queues/semaphores/mutexes/spinlocks.

Possible Fixes and their trade-offs

Reserving the next reader

It might be possible to maintain a next_reader_task field in the queue structure somewhere indicating the task that was just unblocked on the queue. This would mean that any contesting task would need to check if there is a next_reader_task and block themselves even if a message is available. For example, “task A” (priority 5, core 0) has just been unblocked to read the queue, “task B” (priority 4, core 1) gets the critical section first but does not read the message as there is next_read_task is set. "task B’ blocks itself thus allowing “task A” to read the message as intended.

This would solve the immediate race condition mentioned above, but introduces further issues:

• If next_read_task is reserved for “task_A”, but “task A” gets deleted before it can fully loop back around, we will need to maintain another data structure in every task so that the next_read_task can be cleaned up properly.
• What if the next_read_task is reserved for “task A”, and while it is looping back around “task A” gets preempted by a higher priority “task X”, where “task X” continues to run for a long while without yielding to “task A”. Meanwhile, a “task Y” of the same priority as “task A” but on the other core attempts to read the queue which has been reserved for “task A”. In this case…
  • Should “task Y” block and leave the message for “task A”, waiting for “task A” to schedule back to read the message (i.e., strict FIFO order)?
  • Or should “task Y” read the message immediately given that it would be more efficient as “task A” cannot immediately read the message (i.e., first come first serve model)?

Ensuring only the highest priority tasks run

In this approach, only tasks of the current highest priority would run. For example, if the highest ready priority was 10, then only priority 10 tasks would run. If a core does not have an available task of that priority to run, it will run the idle task. This approach is actually provided in Amazon SMP FreeRTOS (see the configRUN_MULTIPLE_PRIORITIES option) and would restore the single core assumption of the highest priority task running at any one time. However, the down side to this is a severe reduction in processing throughput, as the cores cannot run tasks of different priorities at the same time.

If you have any ideas/considerations/suggestions about this issue, I’m happy to hear them.

@Dazza0 Any comment abut this issue? The starvation looks like a fundamental issue.

I tested above code with v5.1-dev-1879-g96b0cb2828 using esp32c3 (which is single core), and confirm the same behavior. i.e. After an initial period, Task A blocks forever while Task B takes and gives the semaphore to itself, starving task A entirely until the loop in Task B exits.

Implications on SMP in IDF

This race condition isn’t an issue in most IDF applications for the following reasons:

But @acf-bwl and @matt-mjm already prove this issue can happen in a real project, especially with “the same priority” case.