Deadlock risk of Immediate Ceiling Priority Protocol (ICPP) with nested resource sharing

[Junjie Shi]

In the current implementation of Immediate Ceiling Priority Protocol (ICPP), the task's base priority is assumed to be lower or equal to the requested resource's ceiling after a successful ceiling check.

However, we notice that the resource's ceiling is not checked against the thread's (task's) base priority but against its current dunamic priority derived from the task's priority aggregation.
According to the definition of priority ceiling, a resource’s ceiling is required to be set as the highest base priority of all tasks that are requesting it.

This mismatch may lead to a deadlock by erroneously denying legitimate nested resource access if resources are requested with descending order of priority ceilings. We give an example to elaborate such a case:
Consider two tasks t_1 and t_2, t_1 has higher priority than t_2 and two resources R_1 (used by both tasks) and R_2 (used by t_2 only) with Ceiling(R_1) = Priority(t_1) and Ceiling(R_2) = Priority(t_2). If t_2 acquires R_1, it inherits its priority ceiling and executes with the promoted dynamic priority Priority(t_1). If it requests the second resource R_2 , its dynamic priority is higher than Ceiling(R_2), which leads to a denial of the resource access by the implemented ceiling check. The consequence of this is a deadlock, i.e., t_2 holds R_1 but cannot successfully lock semaphore R_2 due to the implemented ceiling check, whilst t_1 cannot enter the critical section guarded by R_1.

Such execution behavior with a deadlock can also be demonstrated by a running example in RTEMS, which has been attached.

To correct the mismatch, an adaption to the priority ceiling check is proposed in the attached patch for coremuteximpl.h. Instead of checking the potentially already increased dynamic priority, it uses the thread’s base priority for the comparison to the newly requested resource’s priority ceiling.

After applying the correction, the aforementioned counterexample can be successfully executed.

[Junjie Shi]

ICPP test with deadlock

[Gedare Bloom]

I would like to move this to 5.4 at least. I believe this bug is avoidable by common practice, and deterministically triggered if it will occur. I would isolate the fix to a later dot release to avoid unexpected impacts on other applications.