score: Add deadlock detection

The mutex objects use the owner field of the thread queues for the mutex
owner.  Use this and add a deadlock detection to
_Thread_queue_Enqueue_critical() for thread queues with an owner.

Update #2412.
Update #2556.
Close #2765.

4 files changed, 90 insertions, 2 deletions

diff --git a/cpukit/score/include/rtems/score/interr.h b/cpukit/score/include/rtems/score/interr.h
index 8d4c104e28..845dc6f198 100644
--- a/cpukit/score/include/rtems/score/interr.h
+++ b/cpukit/score/include/rtems/score/interr.h
@@ -163,7 +163,8 @@ typedef enum {
   INTERNAL_ERROR_CPU_ISR_INSTALL_VECTOR,
   INTERNAL_ERROR_RESOURCE_IN_USE,
   INTERNAL_ERROR_RTEMS_INIT_TASK_ENTRY_IS_NULL,
-  INTERNAL_ERROR_POSIX_INIT_THREAD_ENTRY_IS_NULL
+  INTERNAL_ERROR_POSIX_INIT_THREAD_ENTRY_IS_NULL,
+  INTERNAL_ERROR_THREAD_QUEUE_DEADLOCK
 } Internal_errors_Core_list;
 
 typedef CPU_Uint32ptr Internal_errors_t;
diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h
index a52c34f7fd..d03f0c25e5 100644
--- a/cpukit/score/include/rtems/score/thread.h
+++ b/cpukit/score/include/rtems/score/thread.h
@@ -327,6 +327,12 @@ typedef struct {
      */
     Chain_Control Pending_requests;
   } Lock;
+
+  /**
+   * @brief Thread queue link provided for use by the thread wait lock owner to
+   * build a thread queue path.
+   */
+  Thread_queue_Link Link;
 #endif
 
   /**
diff --git a/cpukit/score/include/rtems/score/threadq.h b/cpukit/score/include/rtems/score/threadq.h
index 9a178049ea..a39a031905 100644
--- a/cpukit/score/include/rtems/score/threadq.h
+++ b/cpukit/score/include/rtems/score/threadq.h
@@ -49,6 +49,17 @@ typedef struct Thread_queue_Operations Thread_queue_Operations;
 
 typedef struct Thread_queue_Path Thread_queue_Path;
 
+/**
+ * @brief Thread queue deadlock callout.
+ *
+ * @param the_thread The thread that detected the deadlock.
+ *
+ * @see _Thread_queue_Context_set_deadlock_callout().
+ */
+typedef void ( *Thread_queue_Deadlock_callout )(
+  Thread_Control *the_thread
+);
+
 #if defined(RTEMS_MULTIPROCESSING)
 /**
  * @brief Multiprocessing (MP) support callout for thread queue operations.
@@ -117,6 +128,17 @@ typedef struct {
   uint64_t timeout;
 
   /**
+   * @brief Invoked in case of a detected deadlock.
+   *
+   * Must be initialized for _Thread_queue_Enqueue_critical() in case the
+   * thread queue may have an owner, e.g. for mutex objects.
+   *
+   * @see _Thread_queue_Context_set_deadlock_callout().
+   */
+  Thread_queue_Deadlock_callout deadlock_callout;
+
+#if defined(RTEMS_MULTIPROCESSING)
+  /**
    * @brief Callout to unblock the thread in case it is actually a thread
    * proxy.
    *
@@ -126,7 +148,6 @@ typedef struct {
    *
    * @see _Thread_queue_Context_set_MP_callout().
    */
-#if defined(RTEMS_MULTIPROCESSING)
   Thread_queue_MP_callout mp_callout;
 #endif
 
@@ -175,6 +196,28 @@ typedef struct {
  */
 typedef struct {
   /**
+   * @brief Node to register this link in the global thread queue links lookup
+   * tree.
+   */
+  RBTree_Node Registry_node;
+
+  /**
+   * @brief The source thread queue determined by the thread queue owner.
+   */
+  Thread_queue_Queue *source;
+
+  /**
+   * @brief The target thread queue determined by the thread wait queue of the
+   * source owner.
+   */
+  Thread_queue_Queue *target;
+
+  /**
+   * @brief Node to add this link to a thread queue path.
+   */
+  Chain_Node Path_node;
+
+  /**
    * @brief The owner of this thread queue link.
    */
   Thread_Control *owner;
diff --git a/cpukit/score/include/rtems/score/threadqimpl.h b/cpukit/score/include/rtems/score/threadqimpl.h
index 3d4f6136f6..f0ca614ba1 100644
--- a/cpukit/score/include/rtems/score/threadqimpl.h
+++ b/cpukit/score/include/rtems/score/threadqimpl.h
@@ -52,6 +52,11 @@ extern "C" {
 struct Thread_queue_Path {
 #if defined(RTEMS_SMP)
   /**
+   * @brief The chain of thread queue links defining the thread queue path.
+   */
+  Chain_Control Links;
+
+  /**
    * @brief The start of a thread queue path.
    */
   Thread_queue_Link Start;
@@ -86,6 +91,16 @@ typedef struct {
 } Thread_queue_Syslock_queue;
 
 /**
+ * @brief Sets the thread wait return code to STATUS_DEADLOCK.
+ */
+void _Thread_queue_Deadlock_status( Thread_Control *the_thread );
+
+/**
+ * @brief Results in an INTERNAL_ERROR_THREAD_QUEUE_DEADLOCK fatal error.
+ */
+void _Thread_queue_Deadlock_fatal( Thread_Control *the_thread );
+
+/**
  * @brief Initializes a thread queue context.
  *
  * @param queue_context The thread queue context to initialize.
@@ -97,6 +112,7 @@ RTEMS_INLINE_ROUTINE void _Thread_queue_Context_initialize(
 #if defined(RTEMS_DEBUG)
   memset( queue_context, 0, sizeof( *queue_context ) );
   queue_context->expected_thread_dispatch_disable_level = 0xdeadbeef;
+  queue_context->deadlock_callout = _Thread_queue_Deadlock_fatal;
 #else
   (void) queue_context;
 #endif
@@ -173,6 +189,28 @@ _Thread_queue_Context_set_absolute_timeout(
 }
 
 /**
+ * @brief Sets the deadlock callout in the thread queue
+ * context.
+ *
+ * A deadlock callout must be provided for _Thread_queue_Enqueue_critical()
+ * operations that operate on thread queues which may have an owner, e.g. mutex
+ * objects.  Available deadlock callouts are _Thread_queue_Deadlock_status()
+ * and _Thread_queue_Deadlock_fatal().
+ *
+ * @param queue_context The thread queue context.
+ * @param deadlock_callout The deadlock callout.
+ *
+ * @see _Thread_queue_Enqueue_critical().
+ */
+RTEMS_INLINE_ROUTINE void _Thread_queue_Context_set_deadlock_callout(
+  Thread_queue_Context          *queue_context,
+  Thread_queue_Deadlock_callout  deadlock_callout
+)
+{
+  queue_context->deadlock_callout = deadlock_callout;
+}
+
+/**
  * @brief Sets the MP callout in the thread queue context.
  *
  * @param queue_context The thread queue context.