score: Use priority inheritance for thread join

Threads may join the thread termination of another thread using the
pthread_join() or rtems_task_delete() directives.  The thread cancel operation
used a special case priority boosting mechanism implemented by
_Thread_Raise_real_priority().  The problem was that this approach

* is not transitive,

* does not account for priority adjustments of the calling task
  while waiting for the join,

* does not support clustered scheduling, and

* does not detect deadlocks.

All these problems are fixed by using a priority inheritance thread queue for
the join operation.

Close #4679.

7 files changed, 159 insertions, 143 deletions

diff --git a/cpukit/include/rtems/rtems/tasks.h b/cpukit/include/rtems/rtems/tasks.h
index 81757db8c7..ba05d92531 100644
--- a/cpukit/include/rtems/rtems/tasks.h
+++ b/cpukit/include/rtems/rtems/tasks.h
@@ -413,8 +413,8 @@ rtems_task_priority _RTEMS_Maximum_priority( void );
 /**
  * @ingroup RTEMSAPIClassicTasks
  *
- * @brief This constant variable provides the lowest (least important) task
- *   priority of the first configured scheduler.
+ * @brief This runtime constant represents the lowest (least important) task
+ *   priority of the scheduler with index zero.
  */
 #define RTEMS_MAXIMUM_PRIORITY _RTEMS_Maximum_priority()
 
@@ -1031,13 +1031,25 @@ rtems_status_code rtems_task_restart(
  * @retval ::RTEMS_CALLED_FROM_ISR The directive was called from within
  *   interrupt context.
  *
+ * @retval ::RTEMS_INCORRECT_STATE The task termination procedure was started,
+ *   however, waiting for the terminating task would have resulted in a
+ *   deadlock.
+ *
  * @retval ::RTEMS_ILLEGAL_ON_REMOTE_OBJECT The task resided on a remote node.
  *
  * @par Notes
  * @parblock
- * RTEMS stops the execution of the task and reclaims the stack memory, any
- * allocated delay or timeout timers, the TCB, and, if the task is
- * #RTEMS_FLOATING_POINT, its floating point context area. RTEMS explicitly
+ * The task deletion is done in several steps.  Firstly, the task is marked as
+ * terminating.  While the task life of the terminating task is protected, it
+ * executes normally until it disables the task life protection or it deletes
+ * itself.  A terminating task will eventually stop its normal execution and
+ * start its termination procedure.  The procedure executes in the context of
+ * the terminating task.  The task termination procedure involves the
+ * destruction of POSIX key values and running the task termination user
+ * extensions.  Once complete the execution of the task is stopped and
+ * task-specific resources are reclaimed by the system, such as the stack
+ * memory, any allocated delay or timeout timers, the TCB, and, if the task is
+ * #RTEMS_FLOATING_POINT, its floating point context area.  RTEMS explicitly
  * does not reclaim the following resources: region segments, partition
  * buffers, semaphores, timers, or rate monotonic periods.
  *
@@ -1049,10 +1061,12 @@ rtems_status_code rtems_task_restart(
  * resources and delete itself by restarting it with a special argument or by
  * sending it a message, an event, or a signal.
  *
- * Deletion of the current task (#RTEMS_SELF) will force RTEMS to select
+ * Deletion of the calling task (#RTEMS_SELF) will force RTEMS to select
  * another task to execute.
  *
- * The TCB for the deleted task is reclaimed by RTEMS.
+ * When a task deletes another task, the calling task waits until the task
+ * termination procedure of the task being deleted has completed.  The
+ * terminating task inherits the eligible priorities of the calling task.
  *
  * When a global task is deleted, the task identifier must be transmitted to
  * every node in the system for deletion from the local copy of the global
diff --git a/cpukit/include/rtems/score/threadimpl.h b/cpukit/include/rtems/score/threadimpl.h
index 37932b367d..e6e77b195c 100644
--- a/cpukit/include/rtems/score/threadimpl.h
+++ b/cpukit/include/rtems/score/threadimpl.h
@@ -380,15 +380,23 @@ RTEMS_NO_RETURN void _Thread_Exit(
 );
 
 /**
- * @brief Joins the currently executing thread with the given thread to wait
- *      for.
+ * @brief Joins the currently executing thread with the thread.
  *
- * @param[in, out] the_thread The thread to wait for.
- * @param waiting_for_join The states control for the join.
- * @param[in, out] executing The currently executing thread.
- * @param queue_context The thread queue context.
+ * @param[in, out] the_thread is the thread to join.
+ *
+ * @param waiting_for_join is the thread state for the currently executing
+ *   thread.
+ *
+ * @param[in, out] executing is the currently executing thread.
+ *
+ * @param queue_context[in, out] is the thread queue context.  The caller shall
+ *   have acquired the thread state lock using the thread queue context.
+ *
+ * @retval STATUS_SUCCESSFUL The operation was successful.
+ *
+ * @retval STATUS_DEADLOCK A deadlock occurred.
  */
-void _Thread_Join(
+Status_Control _Thread_Join(
   Thread_Control       *the_thread,
   States_Control        waiting_for_join,
   Thread_Control       *executing,
@@ -396,23 +404,41 @@ void _Thread_Join(
 );
 
 /**
+ * @brief Indicates the resulting state of _Thread_Cancel().
+ */
+typedef enum {
+  /**
+   * @brief Indicates that the thread cancel operation is done.
+   */
+  THREAD_CANCEL_DONE,
+
+  /**
+   * @brief Indicates that the thread cancel operation is in progress.
+   *
+   * The cancelled thread is terminating.  It may be joined.
+   */
+  THREAD_CANCEL_IN_PROGRESS
+} Thread_Cancel_state;
+
+/**
  * @brief Cancels the thread.
  *
- * @param[in, out] the_thread The thread to cancel.
- * @param executing The currently executing thread.
- * @param exit_value The exit value for the thread.
+ * @param[in, out] the_thread is the thread to cancel.
+
+ * @param[in, out] executing is the currently executing thread.
+
+ * @param[in, out] life_states_to_clear is the set of thread life states to
+ *   clear for the thread to cancel.
+
+ * @param exit_value is the exit value for the thread to cancel.
  */
-void _Thread_Cancel(
-  Thread_Control *the_thread,
-  Thread_Control *executing,
-  void           *exit_value
+Thread_Cancel_state _Thread_Cancel(
+  Thread_Control   *the_thread,
+  Thread_Control   *executing,
+  Thread_Life_state life_states_to_clear,
+  void             *exit_value
 );
 
-typedef struct {
-  Thread_queue_Context  Base;
-  Thread_Control       *cancel;
-} Thread_Close_context;
-
 /**
  * @brief Closes the thread.
  *
@@ -420,14 +446,21 @@ typedef struct {
  * case the executing thread is not terminated, then this function waits until
  * the terminating thread reached the zombie state.
  *
- * @param the_thread The thread to close.
- * @param executing The currently executing thread.
- * @param[in, out] context The thread close context.
+ * @param the_thread is the thread to close.
+ *
+ * @param[in, out] executing is the currently executing thread.
+ *
+ * @param[in, out] queue_context is the thread queue context.  The caller shall
+ *   have disabled interrupts using the thread queue context.
+ *
+ * @retval STATUS_SUCCESSFUL The operation was successful.
+ *
+ * @retval STATUS_DEADLOCK A deadlock occurred.
  */
-void _Thread_Close(
+Status_Control _Thread_Close(
   Thread_Control       *the_thread,
   Thread_Control       *executing,
-  Thread_Close_context *context
+  Thread_queue_Context *queue_context
 );
 
 /**
diff --git a/cpukit/posix/src/cancel.c b/cpukit/posix/src/cancel.c
index 300055d68a..0fb2199f0a 100644
--- a/cpukit/posix/src/cancel.c
+++ b/cpukit/posix/src/cancel.c
@@ -75,7 +75,7 @@ int pthread_cancel( pthread_t thread )
   } else {
     _Thread_Dispatch_disable_with_CPU( cpu_self, &lock_context );
     _ISR_lock_ISR_enable( &lock_context );
-    _Thread_Cancel( the_thread, executing, PTHREAD_CANCELED );
+    (void) _Thread_Cancel( the_thread, executing, 0, PTHREAD_CANCELED );
     _Thread_Dispatch_enable( cpu_self );
   }
   return 0;
diff --git a/cpukit/posix/src/pthreadjoin.c b/cpukit/posix/src/pthreadjoin.c
index 84ff15ceec..e4f978f6b4 100644
--- a/cpukit/posix/src/pthreadjoin.c
+++ b/cpukit/posix/src/pthreadjoin.c
@@ -54,26 +54,16 @@ static int _POSIX_Threads_Join( pthread_t thread, void **value_ptr )
 {
   Thread_Control       *the_thread;
   Thread_queue_Context  queue_context;
-  Per_CPU_Control      *cpu_self;
   Thread_Control       *executing;
-  void                 *value;
+  Status_Control        status;
 
   _Thread_queue_Context_initialize( &queue_context );
-  _Thread_queue_Context_set_enqueue_do_nothing_extra( &queue_context );
   the_thread = _Thread_Get( thread, &queue_context.Lock_context.Lock_context );
 
   if ( the_thread == NULL ) {
     return ESRCH;
   }
 
-  cpu_self = _Per_CPU_Get();
-  executing = _Per_CPU_Get_executing( cpu_self );
-
-  if ( executing == the_thread ) {
-    _ISR_lock_ISR_enable( &queue_context.Lock_context.Lock_context );
-    return EDEADLK;
-  }
-
   _Thread_State_acquire_critical(
     the_thread,
     &queue_context.Lock_context.Lock_context
@@ -84,33 +74,20 @@ static int _POSIX_Threads_Join( pthread_t thread, void **value_ptr )
     return EINVAL;
   }
 
-  if ( _States_Is_waiting_for_join_at_exit( the_thread->current_state ) ) {
-    value = the_thread->Life.exit_value;
-    _Thread_Clear_state_locked( the_thread, STATES_WAITING_FOR_JOIN_AT_EXIT );
-    _Thread_Dispatch_disable_with_CPU(
-      cpu_self,
-      &queue_context.Lock_context.Lock_context
-    );
-    _Thread_State_release( the_thread, &queue_context.Lock_context.Lock_context );
-    _Thread_Dispatch_direct( cpu_self );
-  } else {
-    _Thread_Join(
-      the_thread,
-      STATES_INTERRUPTIBLE_BY_SIGNAL | STATES_WAITING_FOR_JOIN,
-      executing,
-      &queue_context
-    );
-
-    if ( _POSIX_Get_error_after_wait( executing ) != 0 ) {
-      _Assert( _POSIX_Get_error_after_wait( executing ) == EINTR );
-      return EINTR;
-    }
-
-    value = executing->Wait.return_argument;
+  executing = _Thread_Executing;
+  status = _Thread_Join(
+    the_thread,
+    STATES_INTERRUPTIBLE_BY_SIGNAL | STATES_WAITING_FOR_JOIN,
+    executing,
+    &queue_context
+  );
+
+  if ( status != STATUS_SUCCESSFUL ) {
+    return _POSIX_Get_error( status );
   }
 
   if ( value_ptr != NULL ) {
-    *value_ptr = value;
+    *value_ptr = executing->Wait.return_argument;
   }
 
   return 0;
diff --git a/cpukit/rtems/src/taskdelete.c b/cpukit/rtems/src/taskdelete.c
index 2e3de0922e..410842f393 100644
--- a/cpukit/rtems/src/taskdelete.c
+++ b/cpukit/rtems/src/taskdelete.c
@@ -40,6 +40,7 @@
 #endif
 
 #include <rtems/rtems/tasksimpl.h>
+#include <rtems/rtems/statusimpl.h>
 #include <rtems/score/threadimpl.h>
 
 rtems_status_code rtems_task_delete(
@@ -47,12 +48,13 @@ rtems_status_code rtems_task_delete(
 )
 {
   Thread_Control       *the_thread;
-  Thread_Close_context  context;
+  Thread_queue_Context  queue_context;
   Per_CPU_Control      *cpu_self;
   Thread_Control       *executing;
+  Status_Control        status;
 
-  _Thread_queue_Context_initialize( &context.Base );
-  the_thread = _Thread_Get( id, &context.Base.Lock_context.Lock_context );
+  _Thread_queue_Context_initialize( &queue_context );
+  the_thread = _Thread_Get( id, &queue_context.Lock_context.Lock_context );
 
   if ( the_thread == NULL ) {
 #if defined(RTEMS_MULTIPROCESSING)
@@ -67,23 +69,22 @@ rtems_status_code rtems_task_delete(
   cpu_self = _Per_CPU_Get();
 
   if ( _Per_CPU_Is_ISR_in_progress( cpu_self ) ) {
-    _ISR_lock_ISR_enable( &context.Base.Lock_context.Lock_context );
+    _ISR_lock_ISR_enable( &queue_context.Lock_context.Lock_context );
     return RTEMS_CALLED_FROM_ISR;
   }
 
   executing = _Per_CPU_Get_executing( cpu_self );
 
   if ( the_thread == executing ) {
-    _ISR_lock_ISR_enable( &context.Base.Lock_context.Lock_context );
+    _ISR_lock_ISR_enable( &queue_context.Lock_context.Lock_context );
 
     /*
      * The Classic tasks are neither detached nor joinable.  In case of
      * self deletion, they are detached, otherwise joinable by default.
      */
     _Thread_Exit( NULL, THREAD_LIFE_TERMINATING | THREAD_LIFE_DETACHED );
-  } else {
-    _Thread_Close( the_thread, executing, &context );
   }
 
-  return RTEMS_SUCCESSFUL;
+  status = _Thread_Close( the_thread, executing, &queue_context );
+  return _Status_Get( status );
 }
diff --git a/cpukit/score/src/threadinitialize.c b/cpukit/score/src/threadinitialize.c
index 457fdaa54a..9b37206c6d 100644
--- a/cpukit/score/src/threadinitialize.c
+++ b/cpukit/score/src/threadinitialize.c
@@ -298,6 +298,7 @@ static bool _Thread_Try_initialize(
   the_thread->Start.is_preemptible        = config->is_preemptible;
   the_thread->Start.cpu_budget_operations = config->cpu_budget_operations;
   the_thread->Start.stack_free            = config->stack_free;
+  the_thread->Join_queue.Queue.owner      = the_thread;
 
   _Thread_Timer_initialize( &the_thread->Timer, cpu );
   _Thread_Initialize_scheduler_and_wait_nodes( the_thread, config );
diff --git a/cpukit/score/src/threadrestart.c b/cpukit/score/src/threadrestart.c
index 25f57e2a40..bcf5dccc69 100644
--- a/cpukit/score/src/threadrestart.c
+++ b/cpukit/score/src/threadrestart.c
@@ -14,7 +14,7 @@
  *  COPYRIGHT (c) 1989-1999.
  *  On-Line Applications Research Corporation (OAR).
  *
- *  Copyright (c) 2014, 2021 embedded brains GmbH.
+ * Copyright (C) 2014, 2022 embedded brains GmbH
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -55,7 +55,7 @@
 #include <rtems/score/userextimpl.h>
 #include <rtems/score/watchdogimpl.h>
 
-#define THREAD_JOIN_TQ_OPERATIONS &_Thread_queue_Operations_priority
+#define THREAD_JOIN_TQ_OPERATIONS &_Thread_queue_Operations_priority_inherit
 
 static void _Thread_Life_action_handler(
   Thread_Control   *executing,
@@ -70,31 +70,6 @@ Thread_Zombie_registry _Thread_Zombies = {
   .Chain = CHAIN_INITIALIZER_EMPTY( _Thread_Zombies.Chain )
 };
 
-static void _Thread_Raise_real_priority(
-  Thread_Control   *the_thread,
-  Priority_Control  priority
-)
-{
-  Thread_queue_Context queue_context;
-
-  _Thread_queue_Context_initialize( &queue_context );
-  _Thread_queue_Context_clear_priority_updates( &queue_context );
-  _Thread_Wait_acquire( the_thread, &queue_context );
-
-  if ( priority < the_thread->Real_priority.priority ) {
-    _Thread_Priority_change(
-      the_thread,
-      &the_thread->Real_priority,
-      priority,
-      PRIORITY_GROUP_LAST,
-      &queue_context
-    );
-  }
-
-  _Thread_Wait_release( the_thread, &queue_context );
-  _Thread_Priority_update( &queue_context );
-}
-
 typedef struct {
   Thread_queue_Context  Base;
   void                 *exit_value;
@@ -388,18 +363,37 @@ static void _Thread_Remove_life_change_request( Thread_Control *the_thread )
   _Thread_State_release( the_thread, &lock_context );
 }
 
-void _Thread_Join(
+static void _Thread_Clear_waiting_for_join_at_exit(
+  Thread_queue_Queue   *queue,
+  Thread_Control       *the_thread,
+  Per_CPU_Control      *cpu_self,
+  Thread_queue_Context *queue_context
+)
+{
+  (void) the_thread;
+  (void) cpu_self;
+  (void) queue_context;
+  _Thread_Clear_state( queue->owner, STATES_WAITING_FOR_JOIN_AT_EXIT );
+}
+
+Status_Control _Thread_Join(
   Thread_Control       *the_thread,
   States_Control        waiting_for_join,
   Thread_Control       *executing,
   Thread_queue_Context *queue_context
 )
 {
-  _Assert( the_thread != executing );
   _Assert( _Thread_State_is_owner( the_thread ) );
 
   executing->Wait.return_argument = NULL;
-
+  _Thread_queue_Context_set_enqueue_callout(
+    queue_context,
+    _Thread_Clear_waiting_for_join_at_exit
+  );
+  _Thread_queue_Context_set_deadlock_callout(
+    queue_context,
+    _Thread_queue_Deadlock_status
+  );
   _Thread_queue_Context_set_thread_state( queue_context, waiting_for_join );
   _Thread_queue_Enqueue(
     &the_thread->Join_queue.Queue,
@@ -407,6 +401,7 @@ void _Thread_Join(
     executing,
     queue_context
   );
+  return _Thread_Wait_get_status( executing );
 }
 
 static void _Thread_Set_exit_value(
@@ -435,15 +430,15 @@ static void _Thread_Try_life_change_request(
   }
 }
 
-void _Thread_Cancel(
-  Thread_Control *the_thread,
-  Thread_Control *executing,
-  void           *exit_value
+Thread_Cancel_state _Thread_Cancel(
+  Thread_Control   *the_thread,
+  Thread_Control   *executing,
+  Thread_Life_state life_states_to_clear,
+  void             *exit_value
 )
 {
-  ISR_lock_Context   lock_context;
-  Thread_Life_state  previous;
-  Per_CPU_Control   *cpu_self;
+  ISR_lock_Context  lock_context;
+  Thread_Life_state previous;
 
   _Assert( the_thread != executing );
 
@@ -452,60 +447,55 @@ void _Thread_Cancel(
   _Thread_Set_exit_value( the_thread, exit_value );
   previous = _Thread_Change_life_locked(
     the_thread,
-    0,
+    life_states_to_clear,
     THREAD_LIFE_TERMINATING,
     0
   );
 
-  cpu_self = _Thread_Dispatch_disable_critical( &lock_context );
-
   if ( _States_Is_dormant( the_thread->current_state ) ) {
     _Thread_State_release( the_thread, &lock_context );
     _Thread_Make_zombie( the_thread );
-  } else {
-    Priority_Control priority;
-
-    _Thread_Try_life_change_request( the_thread, previous, &lock_context );
-    priority = _Thread_Get_priority( executing );
-    _Thread_Raise_real_priority( the_thread, priority );
+    return THREAD_CANCEL_DONE;
   }
 
-  _Thread_Dispatch_enable( cpu_self );
+  _Thread_Try_life_change_request( the_thread, previous, &lock_context );
+  return THREAD_CANCEL_IN_PROGRESS;
 }
 
-static void _Thread_Close_enqueue_callout(
-  Thread_queue_Queue   *queue,
+Status_Control _Thread_Close(
   Thread_Control       *the_thread,
-  Per_CPU_Control      *cpu_self,
+  Thread_Control       *executing,
   Thread_queue_Context *queue_context
 )
 {
-  Thread_Close_context *context;
-
-  context = (Thread_Close_context *) queue_context;
-  _Thread_Cancel( context->cancel, the_thread, NULL );
-}
+  Per_CPU_Control    *cpu_self;
+  Thread_Cancel_state cancel_state;
 
-void _Thread_Close(
-  Thread_Control       *the_thread,
-  Thread_Control       *executing,
-  Thread_Close_context *context
-)
-{
-  context->cancel = the_thread;
-  _Thread_queue_Context_set_enqueue_callout(
-    &context->Base,
-    _Thread_Close_enqueue_callout
+  cpu_self = _Thread_Dispatch_disable_critical(
+    &queue_context->Lock_context.Lock_context
   );
+  _ISR_lock_ISR_enable( &queue_context->Lock_context.Lock_context );
+
+  cancel_state =
+    _Thread_Cancel( the_thread, executing, THREAD_LIFE_DETACHED, NULL );
+
+  if ( cancel_state == THREAD_CANCEL_DONE ) {
+    _Thread_Dispatch_enable( cpu_self );
+    return STATUS_SUCCESSFUL;
+  }
+
+  _ISR_lock_ISR_disable( &queue_context->Lock_context.Lock_context );
+  _Thread_Dispatch_unnest( cpu_self );
   _Thread_State_acquire_critical(
     the_thread,
-    &context->Base.Lock_context.Lock_context
+    &queue_context->Lock_context.Lock_context
   );
-  _Thread_Join(
+
+  return _Thread_Join(
     the_thread,
     STATES_WAITING_FOR_JOIN,
     executing,
-    &context->Base
+    queue_context
   );
 }