Why vTaskPrioritySet doesn't set xEventListItem value according to uxPriority?

Kernel
1

Hello, I was reading the code of vTaskPrioritySet() in tasks.c.

And I found the API just set value of xEventListItem depends on uxNewPriority directly.

If the target task didn’t use inherited uxPriority, then that would be fine. Because uxBasePriority == uxPriority == uxNewPriority at the time of setting.

But if the target task was using inherited uxPriority, we would get different results.

  1. uxNewPriority == uxPriority > uxBasePriority
    1. uxPriority no change
    2. uxBasePriority = uxNewPriority
  2. uxNewPriority > uxPriority > uxBasePriority
    1. uxPriority = uxNewPriority
    2. uxBasePriority = uxNewPriority
  3. (uxNewPriority < uxPriority) && (uxNewPriority != uxBasePriority)
    1. uxPriority no change
    2. uxBasePriority = uxNewPriority

And the value of xEventListItem will be set to (configMAX_PRIORITIES - uxNewPriority) without regard to the uxPriority.

Then we could get some fun results:

ex. 
uxPriority = 20;
uxBasePriority = 2;
uxNewPriority = 1;

xEventListItemValue = (configMAX_PRIORITIES - uxNewPriority) = 32 - 1 = 31;
uxPriority + xEventListItemValue = 20 + 31 = 51;

With a not matched event item value, a high priority task would be put in an incorrect location in an event list when going to block on a kernel object. Then another lower priority tasks will always sit before the high priority task. And the high priority task will never get unblocked. That could be not easy to debug, since we used to check priority of a task instead of event item value. (We can get uxPriority and uxBasePriority by API now. There has no API to get event item value so far. It may be a good idea to add an API for it. But event item value only be used in kernel basically.)

I then checked xTaskPriorityInherit() and vTaskPriorityDisinheritAfterTimeout(). These two APIs are used in mutex mechanism. And they handle event item value depends on inherited uxPriority.

I also did some test on RP2040 to verify the behavior of vTaskPrioritySet() : vTaskPrioritySet_event_item_value .

pre-condition:
task1 priority = 1;
task2 priority = 4;
task1 hold mutex1;

Some simplified console output:

///// task2 try to take mutex1
task2 take mutex1] try

///// task1 inherited priority from task2
task1 on core 0, pri=4, base_pri=1, evt_val=28, ct=1

task1 on core 0, pri=4, base_pri=1, evt_val=28, ct=2

///// set task1 it's own priority = 2
task1 set priority = 2.

///// task1 priority = 4, event value = 30, 4 + 30 = 34 > 32 == configMAX_PRIORITIES
task1 on core 1, pri=4, base_pri=2, evt_val=30, ct=3

I tried to search topics in forum as well:

  • An old topic about adding behavior to set event item value.
  • An topic talking about why not to reinsert an event item after set priority dynamically.
  • That would be an non-deterministic activity. Since unknown number of tasks could block on the same kernel object (ex. an event_group). The event item list would have unknown length. So the reinsertion may cost unknown time.
  • What I thought is:
    • Even though we are not going to reinsert event item. The value still matters to the tasks which are going to block itself.
  • A 2023 post, which opened a PR: Use the bigger priority whenever possible.
  • The commit 60ef67c added dynamic priority change when a task is using an inherited uxPriority.
  • The code before this commit also changes event item value without regard to uxPriority.

That’s what I’ve done so far.

Thanks.

2

Hi @wirelinker,

I’m not quite sure what you want to express with those elaborations. Do you believe that there is an error in the code or just some resulting unintuitive behavior?

I’m afraid I can only repeat what I wrote in the thread you reference: A dynamic temporary priority boost should in my opinion be transparent to other threads. Otherwise there is a new wormhole opening up for new race conditions as outlined in this example:

task A’s base pri: 1 (low)
task B’s base pri: 10 (high)

Now let task A own a mutex and let task B attempt to claim that mutex. The priority inheritance mechanism will now execute A at pri 10 until A releases the mutex.

Now let task C (for whatever reason) query task A’s priority. As you correctly point out, 1 (its base priority) does not reflect the current priority A runs on. So you suggest that C should obtain the value 10 as the correct current priority of A, right?

Two observations come to mind:

  1. For C to even get to the point where it can query A’s priority, either C must execute at a priority higher than 10 itself, or A must temporarily be suspended on another object, allowing C to execute and query A’s priority. Now this gets pretty messy as we now need to make the case distinction, which means query not only A’s current execution priority but also its suspension state - otherwise (ie if C is running on higher pri than A’s current OR base priority), I find it hard to come up with a use case in which C could make use of the information.
  2. In either case, there always is potential for a race condition in which task A’s temporary raised (inherited) priority is lost during the time it is being queried by C and evaulated. Like so:
  • A claims the mutex, runs at pri 1
  • B requests the mutex => A is raised to 10
  • C queries A’s current priority, finds 10 in the architecture you propose
  • A preempts C, releases its mutex, As current priority reverted to 1
  • C now has the wrong (outdated) information about As priority.

Again, if C always runs at higher priority than A in base OR Inherited priority AND C never releases its time slice (eg due to an own suspension), this race condition won’t happen, but that scenario, again, to me is fairly trivial.

It is my gut feeling (stemming from decades of embedded software design) that fringe conditions like these - unless they lead to truly erroneous scenarios like crashes or deadlocks - do not deserve special treatment. In most cases, muteces should be held as short as possible anyways (and a second rule of good practice is that a task holding a mutex should normally not get suspended while holding the mutex), and any code outside of the tasks not participating in the resource protected by the mutex should not be affected by the mutex at all.

Can you sketch a real life use case in which that scenario should be addressed?

3

Hello @RAc . Thank you for your patience.

The objective I would like to discuss about is the Event Item Value, which corresponds to (configMaxPriority - priority). The reason why I listed the previous topics in forum is because I would like to check the history of the code of vTaskPrioritySet.

I have no question about the scenario you talked in the reply. In fact, task C could have the same priority as task A(after inherited priority to 10). Because it’s under time slicing condition, task C and task A would share CPU time between each other. If we talk about SMP port, task A and task C could be executed on different cores at the same time. The conclusion is still the same. The priority of task A be queried by task C would be outdated at some point. And I am not going to see this as an error or bug.

So the question is about the Event Item Value. As I showed above, if we set a task’s priority after the task inherited a higher priority. We could get an EventItem Value, which depends on uxNewPriority instead of uxPriority. And as we know, event item value is used by kernel when inserting event item into an ordered waiting list when a task waiting for a kernel object. If the value doesn’t correspond to the uxPriority, then there could be some problem.

  • For some real life example:

TaskA: Pri = 1, using the UART_0, communication task between an MCU and an SBC(Raspberry Pi).

TaskB: Pri = 4, using UART_0, BLE task, basically waiting for an interrupt from BLE module.

TaskC: Pri = 3, using SPI_1 to LCD, UI task, read graphics from SPI flash memoy then display on LCD repeatedly.

TaskD: Pri = 3, using SPI_2 to GPS, GPS task, control GPS and write GPS NMEA sentence data to SPI flash memory repeatedly.

SPI flash memory, using SPI_0.

MutexA: UART_0

MutexB: SPI_0, for SPI flash

  • Start:

TaskC is reading graphics from flash(MutexB) then writing to LCD and TaskD reading from GPS then write data into flash memory (MutexB) repeatedly.

TaskA was talking to SBC(TaskA hold MutexA). TaskB got an interrupt from BLE module, then TaskB try to take MutexA. TaskB blocked on MutexA. TaskA inherited pri=4.

After some information exchange. The SBC now ask TaskA to receive a file(ex. GPS Constellation Status) and save it into flash memory. Then TaskA elevated it’s own priority to 2, so that it can have better response for receiving the data and then write to flash memory.

Now the TaskA is (pri = 4, base_pri = 2, event item value = 30, hold MutexA).

TaskA receives the data from SBC then try to write into flash(try to take MutexB).

But MutexB was held by TaskC. And TaskD is waiting for MutexB.

TaskA will be blocked and the event item will be inserted into the waiting list of MutexB. TaskC inherited priority from TaskA.

The event item of TaskA will be inserted behind TaskD. Because TaskD is (pri =3, base_pri=3, event item value = 29). So after the TaskC gave back MutexB, TaskD will be unblocked instead of TaskA.

If TaskC and TaskD occupied the whole time of SPI_0 (high graphics refresh rate, intense reading of NMEA sentence ), then TaskA will never get unblocked. Even though TaskA has higher priority.

Then TaskB(BLE task), will never be able to use BLE module(MutexA).

  • For some real test code

I tried to verify this with some test code. vTaskPrioritySet_event_item_value

The test case is slightly different from the above example. Because I let Task3 and Task4 try to take mutex1 after take mutex2. Just like TaskC and TaskD try to send data back to SBC through UART_0 in above example. Which would be more complex.

The result is deadlock randomly. Because I tuned the timing of Task3 and Task4.

///// task2 try to take mutex1
task2 take mutex1] try
task3 take mutex[1] failed
task3 gave mutex[2]
task4 take mutex[2] success
task4 take mutex[1] try
task3 on core 1, pri=3, base_pri=3, evt_val=29, ct=2
task3 take mutex[2] try
///// task1 inherited priority from task2
task1 on core 0, pri=4, base_pri=1, evt_val=28, ct=1
task4 take mutex[1] failed
task4 gave mutex[2]
task3 take mutex[2] success
task4 on core 1, pri=3, base_pri=3, evt_val=29, ct=2
task1 on core 0, pri=4, base_pri=1, evt_val=28, ct=2
///// set task1 it's own priority = 2
task1 set priority = 2.
task4 take mutex[2] try
task3 take mutex[1] try
///// task1 priority = 4, event value = 30, 4 + 30 = 34 > 32 == configMAX_PRIORITIES
task1 on core 1, pri=4, base_pri=2, evt_val=30, ct=3
/////  task1 try to take mutex2
task1 try to take mutex[2] and block indefinitely.
///// task3 and task4 take mutex2 then mutex1 repeatedly
task3 take mutex[1] failed
task3 gave mutex[2]
task4 take mutex[2] success
task3 on core 0, pri=3, base_pri=3, evt_val=29, ct=3
task3 take mutex[2] try
task4 take mutex[1] try
task4 take mutex[1] failed
task4 gave mutex[2]
task3 take mutex[2] success
task3 take mutex[1] try
task4 on core 1, pri=3, base_pri=3, evt_val=29, ct=3
task4 take mutex[2] try
task3 take mutex[1] failed
task3 gave mutex[2]
task4 take mutex[2] success

I also opened an issue on github. [BUG] vTaskPrioritySet doesn't set event item value according to the inherited priority · Issue #1364 · FreeRTOS/FreeRTOS-Kernel · GitHub

But looks like it needs some more general discussion. So I came to here and made this post.

Thank you for your patience again. It’s sensitive to change kernel code. So I thought it is worth more discussion in detail.

4

ok, thanks for the detailed explanation. The one thing I do not understand about your system is UART0. Your description reads as if you overload the UART to communicate both against an RPi and a bluetooth module? How is that supposed to work? Is there an RS485 bus attached, and if yes, what instance is the bus master?

Likely that may be a detail irrelevant to your observations, but I still would like to understand what is going on.

Thanks!

5

The UART0 is protected by MutexA. Every task going to use it should take MutexA first. And BLE module sends notification by using interrupt to MCU, then the task responsible to handle it will try to take the MutexA. And when RPI trying to send data to MCU when BLE is sending/receiving data. It’s a problem. Maybe use RTS, CTS would be better.

In fact, this example is from the combination of my experience and imagination when I was riding a train. Don’t worry. Changing the UART to other kind of bus will still stand for the case. (Maybe I2C would be better.) :rofl: Thank you.

6

Additional Context:

The SPI bus to flash memory is a real story. When I was working for a project before. The previous engineer wrote the code to access flash memory did some bad thing. Some tasks access flash by using file system, some through SPI HAL API directly. No mutex protection. And our system log just gone, randomly. It’s a messy experience. :melting_face::hot_face:

7

ok, I see… I basically tend to agree with the solution that vTaskSetPriority() should fail if the task is subject to inheritance and the target (newly desired) priority is below the boosted priority. Yet I was under the impression that that is exactly what PR Use the bigger priority whenever possible. by Moral-Hao · Pull Request #760 · FreeRTOS/FreeRTOS-Kernel · GitHub was all about? Or did you observe that the access issue still occurs with the merged PR in place?

8

I was thinking about that PR as well. And I found that doesn’t matter.

Because the following code was never changed since this post: two bugs in tasks.c.

listSET_LIST_ITEM_VALUE( &( pxTCB->xEventListItem ), ( ( TickType_t ) configMAX_PRIORITIES - ( TickType_t ) uxNewPriority ) );

The event item value just depends on uxNewPriority directly. No matter where the uxPriority or uxBasePriority came from. So, we could still get same problem if we use older code before the PR “Use the bigger priority whenever possible.#760”. The commit 60ef67c only changed the condition:

from

if( pxTCB->uxBasePriority == pxTCB->uxPriority )

to

if( ( pxTCB->uxBasePriority == pxTCB->uxPriority ) || ( uxNewPriority > pxTCB->uxPriority ) )

But that doesn’t matter at all. :sweat_smile:

If we use the code before the PR#760.

  • for the “imagined“ real life example (if we fix the blind spot of UART bus usage.)

The problem would still be there.

  • for the real test code

The problem would still be there. Because the critical part of code is the same.

The reason why we focus on the priority of a task may due to the priority is one of the most basic concept in kernel. In fact, if we set the event item value corresponding to uxPriority, it would be more stable. Because if

  1. The priority is not inherited, then the event item value should be changed depends on uxPriority.
  2. The priority is inherited, then the event item value should still be changed depends on uxPriority. It’s not a question about the vTaskPrioritySet should fail or not. The event item value would not be fiddled like the uxBasePriority. So it’s more stable and sensible.

Additional about the real life example:

If we use a timeout when TaskB waiting for the bus to BLE. Then TaskA’s event item would be reset to a correct value due to the disinheritance after timeout. And the deadlock would disappear. The cost is the communication error of BLE module and retry. In fact, this example is buggy. The taskA should use the same priority with TaskC, D if the TaskC, D has intense usage of SPI flash. If taskA use a priority lower than TaskC,D, it should expect a longer wait latency. So the only problem we could address from the example is when TaskA inherit higher priority from TaskB. Then TaskD should be unblocked after TaskA. But it wouldn’t work like this. Then TaskA may still wait for a long latency as usual. And TaskB would still have timeout error, due to the higher priority should expect shorter wait latency.

We may be used to set a timeout when taking a mutex. So it changes from a deadlock to some random error. That’s why I set an indeterminate wait timeout in test code to emphasize the problem. And it looks like an incomplete feature of vTaskPrioritySet.

1 Like
9

Ah ok.

I do not argue with your analysis, it is very diligent, thorough and sound.

I will agree that dynamic priorities are not handled consistently in FeeRTOS when it comes to mixed manual and automatic (inheritance induced) priority manipulation. Priority inheritance in FreeRTOS is implemented rather rundimentarily anyways, this has been discussed before several times (for example, cascading inheritance is not supported), the reason (I believe) being both footprint and stability considerations. A number of possible improvements have been discussed over the years, but apparently, the use case pressure has never been convincingly strong enough.

Your use case (if I read it correctly) is one that has been discussed several times on this forum, and I repeatedly argue that it is faulty. A serial device (such as your UART0) is by name and definition serial, so attempting to access it concurrently is mismodelling it, inevitably raising follow up problems. In all stable code bases I have worked with it, a physical serial device is being served by a single task that normally implements a message pump, serving client task requests in an ordered and serial fashion with no immanent danger of problems due to concurrent access.

In my understanding, your need to apply application-induced priority changes that compete with inherited priorities is a follow up problem from that mismodel. In the single task driver solution I sketched above, it is possible to prioritize the client requests by feeding the message pump queue not FIFO but both back and front or multi level and thus there will not be a need to mess with task priorities at all.

Apologies if I should misread your use case, but I believe that in this case the problems (correctly identified by you) would be a no issue if the application is rearchitected. It is nevertheless worthwhile discussing the implementation problem you unearthed, but again, unless there are convincing use cases that would justify it, I would vote for making application level (ie calls to vTaskSetPriority()) and system induced (subjected to inheritance) priority changes mutually exclusive. So my solution then would be to have vTaskSetPriority() unconditionally return an error when applied to a task subjected to priority inheritance, otherwise an abyss of race conditions and follow up issues opens up, with few real life use cases justifying those risks.

Just my $0.02.

1 Like
10

As you said, it’s an implementation problem.

I am not going to argue with vTaskPrioritySet should return a fail or not.

Because I am a user of the wheel, not the builder. As long as a round wheel could be used, there has no need to use a square wheel.

And it’s not an ideal wheel to everyone. So what I did was to find a corner of a corner case of the implementation.

That’s still fun. Thank you.

1 Like