[RTEMS Project] #4742: Deadlock risk of Immediate Ceiling Priority Protocol (ICPP) with nested resource sharing

[RTEMS trac]

#4742: Deadlock risk of Immediate Ceiling Priority Protocol (ICPP) with nested
resource sharing
-------------------------+----------------------------------------
  Reporter:  Junjie Shi  |      Owner:  (none)
      Type:  defect      |     Status:  new
  Priority:  normal      |  Milestone:  5.1
 Component:  rtems       |    Version:  5
  Severity:  normal      |   Keywords:  Resource sharing, deadlock
Blocked By:              |   Blocking:
-------------------------+----------------------------------------
 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.

--
Ticket URL: <http://devel.rtems.org/ticket/4742>
RTEMS Project <http://www.rtems.org/>
RTEMS Project