score: More thread queue operations

Move thread queue discipline specific operations into
Thread_queue_Operations.  Use a separate node in the thread control
block for the thread queue to make it independent of the scheduler data
structures.

Update #2273.

10 files changed, 282 insertions, 92 deletions

diff --git a/cpukit/posix/src/killinfo.c b/cpukit/posix/src/killinfo.c
index 5d3dded53f..c8c59d6096 100644
--- a/cpukit/posix/src/killinfo.c
+++ b/cpukit/posix/src/killinfo.c
@@ -146,7 +146,7 @@ int killinfo(
         !_Chain_Is_tail( the_chain, the_node ) ;
         the_node = the_node->next ) {
 
-    the_thread = (Thread_Control *)the_node;
+    the_thread = THREAD_CHAIN_NODE_TO_THREAD( the_node );
     api = the_thread->API_Extensions[ THREAD_API_POSIX ];
 
     #if defined(DEBUG_SIGNAL_PROCESSING)
diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h
index bce6f5643e..b6662e49af 100644
--- a/cpukit/score/include/rtems/score/thread.h
+++ b/cpukit/score/include/rtems/score/thread.h
@@ -286,6 +286,21 @@ typedef unsigned int Thread_Wait_flags;
  *  blocked and to return information to it.
  */
 typedef struct {
+  /**
+   * @brief Node for thread queues.
+   */
+  union {
+    /**
+     * @brief A node for chains.
+     */
+    Chain_Node Chain;
+
+    /**
+     * @brief A node for red-black trees.
+     */
+    RBTree_Node RBTree;
+  } Node;
+
   /** This field is the Id of the object this thread is waiting upon. */
   Objects_Id            id;
   /** This field is used to return an integer while when blocked. */
@@ -349,8 +364,6 @@ typedef struct {
 typedef struct {
   /** This field is the object management structure for each proxy. */
   Objects_Control          Object;
-  /** This field is used to enqueue the thread on RBTrees. */
-  RBTree_Node              RBNode;
   /** This field is the current execution state of this proxy. */
   States_Control           current_state;
   /** This field is the current priority state of this proxy. */
@@ -638,8 +651,6 @@ typedef struct {
 struct Thread_Control_struct {
   /** This field is the object management structure for each thread. */
   Objects_Control          Object;
-  /** This field is used to enqueue the thread on RBTrees. */
-  RBTree_Node              RBNode;
   /** This field is the current execution state of this thread. */
   States_Control           current_state;
   /** This field is the current priority state of this thread. */
diff --git a/cpukit/score/include/rtems/score/threadimpl.h b/cpukit/score/include/rtems/score/threadimpl.h
index 953b88b925..b8c235c846 100644
--- a/cpukit/score/include/rtems/score/threadimpl.h
+++ b/cpukit/score/include/rtems/score/threadimpl.h
@@ -78,8 +78,11 @@ SCORE_EXTERN Thread_Control *_Thread_Allocated_fp;
 SCORE_EXTERN struct _reent **_Thread_libc_reent;
 #endif
 
+#define THREAD_CHAIN_NODE_TO_THREAD( node ) \
+  RTEMS_CONTAINER_OF( node, Thread_Control, Wait.Node.Chain )
+
 #define THREAD_RBTREE_NODE_TO_THREAD( node ) \
-  RTEMS_CONTAINER_OF( node, Thread_Control, RBNode )
+  RTEMS_CONTAINER_OF( node, Thread_Control, Wait.Node.RBTree )
 
 #if defined(RTEMS_SMP)
 #define THREAD_RESOURCE_NODE_TO_THREAD( node ) \
diff --git a/cpukit/score/include/rtems/score/threadq.h b/cpukit/score/include/rtems/score/threadq.h
index c483b87620..59781ac73c 100644
--- a/cpukit/score/include/rtems/score/threadq.h
+++ b/cpukit/score/include/rtems/score/threadq.h
@@ -49,14 +49,81 @@ typedef struct Thread_queue_Control Thread_queue_Control;
  *
  * @param[in] the_thread The thread.
  * @param[in] new_priority The new priority value.
- * @param[in] queue The thread queue.
+ * @param[in] the_thread_queue The thread queue.
  *
  * @see Thread_queue_Operations.
  */
 typedef void ( *Thread_queue_Priority_change_operation )(
   Thread_Control       *the_thread,
   Priority_Control      new_priority,
-  Thread_queue_Control *queue
+  Thread_queue_Control *the_thread_queue
+);
+
+/**
+ * @brief Thread queue initialize operation.
+ *
+ * @param[in] the_thread_queue The thread queue.
+ *
+ * @see _Thread_Wait_set_operations().
+ */
+typedef void ( *Thread_queue_Initialize_operation )(
+  Thread_queue_Control *the_thread_queue
+);
+
+/**
+ * @brief Thread queue enqueue operation.
+ *
+ * @param[in] the_thread_queue The thread queue.
+ * @param[in] the_thread The thread to enqueue on the queue.
+ *
+ * @see _Thread_Wait_set_operations().
+ */
+typedef void ( *Thread_queue_Enqueue_operation )(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
+);
+
+/**
+ * @brief Thread queue dequeue operation.
+ *
+ * @param[in] the_thread_queue The thread queue.
+ *
+ * @retval NULL No thread is present on the thread queue.
+ * @retval first The first thread of the thread queue according to the insert
+ * order.  This thread is no longer on the thread queue.
+ *
+ * @see _Thread_Wait_set_operations().
+ */
+typedef Thread_Control *( *Thread_queue_Dequeue_operation )(
+  Thread_queue_Control *the_thread_queue
+);
+
+/**
+ * @brief Thread queue extract operation.
+ *
+ * @param[in] the_thread_queue The thread queue.
+ * @param[in] the_thread The thread to extract from the thread queue.
+ *
+ * @see _Thread_Wait_set_operations().
+ */
+typedef void ( *Thread_queue_Extract_operation )(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
+);
+
+/**
+ * @brief Thread queue first operation.
+ *
+ * @param[in] the_thread_queue The thread queue.
+ *
+ * @retval NULL No thread is present on the thread queue.
+ * @retval first The first thread of the thread queue according to the insert
+ * order.  This thread remains on the thread queue.
+ *
+ * @see _Thread_Wait_set_operations().
+ */
+typedef Thread_Control *( *Thread_queue_First_operation )(
+  Thread_queue_Control *the_thread_queue
 );
 
 /**
@@ -76,6 +143,39 @@ typedef struct {
    * to be done during a priority change.
    */
   Thread_queue_Priority_change_operation priority_change;
+
+  /**
+   * @brief Thread queue initialize operation.
+   *
+   * Called by object initialization routines.
+   */
+  Thread_queue_Initialize_operation initialize;
+
+  /**
+   * @brief Thread queue enqueue operation.
+   *
+   * Called by object routines to enqueue the thread.
+   */
+  Thread_queue_Enqueue_operation enqueue;
+
+  /**
+   * @brief Thread queue dequeue operation.
+   *
+   * Called by object routines to dequeue the first waiting thread if present.
+   */
+  Thread_queue_Dequeue_operation dequeue;
+
+  /**
+   * @brief Thread queue extract operation.
+   *
+   * Called by object routines to extract a thread from a thread queue.
+   */
+  Thread_queue_Extract_operation extract;
+
+  /**
+   * @brief Thread queue first operation.
+   */
+  Thread_queue_First_operation first;
 } Thread_queue_Operations;
 
 /**
@@ -120,8 +220,6 @@ struct Thread_queue_Control {
 
   /** This field is used to manage the critical section. */
   Thread_blocking_operation_States sync_state;
-  /** This field indicates the thread queue's blocking discipline. */
-  Thread_queue_Disciplines discipline;
   /** This is the status value returned to threads which timeout while
    *  waiting on this thread queue.
    */
diff --git a/cpukit/score/src/thread.c b/cpukit/score/src/thread.c
index f4c53079d5..8a34ced684 100644
--- a/cpukit/score/src/thread.c
+++ b/cpukit/score/src/thread.c
@@ -28,7 +28,6 @@
   )
 
 THREAD_OFFSET_ASSERT( Object );
-THREAD_OFFSET_ASSERT( RBNode );
 THREAD_OFFSET_ASSERT( current_state );
 THREAD_OFFSET_ASSERT( current_priority );
 THREAD_OFFSET_ASSERT( real_priority );
diff --git a/cpukit/score/src/threadq.c b/cpukit/score/src/threadq.c
index 47c294e968..61832c19a2 100644
--- a/cpukit/score/src/threadq.c
+++ b/cpukit/score/src/threadq.c
@@ -19,9 +19,7 @@
 #endif
 
 #include <rtems/score/threadqimpl.h>
-#include <rtems/score/chainimpl.h>
 #include <rtems/score/rbtreeimpl.h>
-#include <rtems/score/scheduler.h>
 #include <rtems/score/threadimpl.h>
 
 RBTree_Compare_result _Thread_queue_Compare_priority(
@@ -51,15 +49,20 @@ void _Thread_queue_Initialize(
   uint32_t                      timeout_status
 )
 {
-  the_thread_queue->discipline     = the_discipline;
+  const Thread_queue_Operations *operations;
+
   the_thread_queue->timeout_status = timeout_status;
   the_thread_queue->sync_state     = THREAD_BLOCKING_OPERATION_SYNCHRONIZED;
 
   _ISR_lock_Initialize( &the_thread_queue->Lock, "Thread Queue" );
 
   if ( the_discipline == THREAD_QUEUE_DISCIPLINE_PRIORITY ) {
-    _RBTree_Initialize_empty( &the_thread_queue->Queues.Priority );
-  } else { /* must be THREAD_QUEUE_DISCIPLINE_FIFO */
-    _Chain_Initialize_empty( &the_thread_queue->Queues.Fifo );
+    operations = &_Thread_queue_Operations_priority;
+  } else {
+    _Assert( the_discipline == THREAD_QUEUE_DISCIPLINE_FIFO );
+    operations = &_Thread_queue_Operations_FIFO;
   }
+
+  the_thread_queue->operations = operations;
+  ( *operations->initialize )( the_thread_queue );
 }
diff --git a/cpukit/score/src/threadqenqueue.c b/cpukit/score/src/threadqenqueue.c
index 6cc731e282..be08ffcbf1 100644
--- a/cpukit/score/src/threadqenqueue.c
+++ b/cpukit/score/src/threadqenqueue.c
@@ -20,7 +20,6 @@
 
 #include <rtems/score/threadqimpl.h>
 #include <rtems/score/assert.h>
-#include <rtems/score/rbtreeimpl.h>
 #include <rtems/score/threadimpl.h>
 #include <rtems/score/watchdogimpl.h>
 
@@ -47,6 +46,7 @@ static void _Thread_blocking_operation_Finalize(
    * The thread is not waiting on anything after this completes.
    */
   _Thread_Wait_set_queue( the_thread, NULL );
+  _Thread_Wait_restore_default_operations( the_thread );
 
   _Thread_Lock_restore_default( the_thread );
 
@@ -127,28 +127,14 @@ void _Thread_queue_Enqueue_critical(
   the_thread_queue->sync_state = THREAD_BLOCKING_OPERATION_SYNCHRONIZED;
 
   if ( sync_state == THREAD_BLOCKING_OPERATION_NOTHING_HAPPENED ) {
-    /*
-     * Invoke the discipline specific enqueue method.
-     */
-    if ( the_thread_queue->discipline == THREAD_QUEUE_DISCIPLINE_FIFO ) {
-      _Chain_Append_unprotected(
-        &the_thread_queue->Queues.Fifo,
-        &the_thread->Object.Node
-      );
-    } else { /* must be THREAD_QUEUE_DISCIPLINE_PRIORITY */
-      _Thread_Wait_set_operations(
-        the_thread,
-        &_Thread_queue_Operations_priority
-      );
-      _RBTree_Insert(
-        &the_thread_queue->Queues.Priority,
-        &the_thread->RBNode,
-        _Thread_queue_Compare_priority,
-        false
-      );
-    }
+    const Thread_queue_Operations *operations;
 
     the_thread_queue->sync_state = THREAD_BLOCKING_OPERATION_SYNCHRONIZED;
+
+    operations = the_thread_queue->operations;
+    _Thread_Wait_set_operations( the_thread, operations );
+    ( *operations->enqueue )( the_thread_queue, the_thread );
+
     _Thread_queue_Release( the_thread_queue, lock_context );
   } else {
     /* Cancel a blocking operation due to ISR */
@@ -181,15 +167,7 @@ void _Thread_queue_Extract_with_return_code(
 
   _SMP_Assert( lock == &the_thread_queue->Lock );
 
-  if ( the_thread_queue->discipline == THREAD_QUEUE_DISCIPLINE_FIFO ) {
-    _Chain_Extract_unprotected( &the_thread->Object.Node );
-  } else { /* must be THREAD_QUEUE_DISCIPLINE_PRIORITY */
-    _RBTree_Extract(
-      &the_thread->Wait.queue->Queues.Priority,
-      &the_thread->RBNode
-    );
-    _Thread_Wait_restore_default_operations( the_thread );
-  }
+  ( *the_thread_queue->operations->extract )( the_thread_queue, the_thread );
 
   the_thread->Wait.return_code = return_code;
 
@@ -217,27 +195,9 @@ Thread_Control *_Thread_queue_Dequeue(
   ISR_lock_Context                  lock_context;
   Thread_blocking_operation_States  sync_state;
 
-  the_thread = NULL;
   _Thread_queue_Acquire( the_thread_queue, &lock_context );
 
-  /*
-   * Invoke the discipline specific dequeue method.
-   */
-  if ( the_thread_queue->discipline == THREAD_QUEUE_DISCIPLINE_FIFO ) {
-    if ( !_Chain_Is_empty( &the_thread_queue->Queues.Fifo ) ) {
-      the_thread = (Thread_Control *)
-       _Chain_Get_first_unprotected( &the_thread_queue->Queues.Fifo );
-    }
-  } else { /* must be THREAD_QUEUE_DISCIPLINE_PRIORITY */
-    RBTree_Node    *first;
-
-    first = _RBTree_Get( &the_thread_queue->Queues.Priority, RBT_LEFT );
-    if ( first ) {
-      the_thread = THREAD_RBTREE_NODE_TO_THREAD( first );
-      _Thread_Wait_restore_default_operations( the_thread );
-    }
-  }
-
+  the_thread = ( *the_thread_queue->operations->dequeue )( the_thread_queue );
   if ( the_thread == NULL ) {
     /*
      * We did not find a thread to unblock in the queue.  Maybe the executing
diff --git a/cpukit/score/src/threadqfirst.c b/cpukit/score/src/threadqfirst.c
index f43b9abbd0..553b28bf62 100644
--- a/cpukit/score/src/threadqfirst.c
+++ b/cpukit/score/src/threadqfirst.c
@@ -19,29 +19,12 @@
 #endif
 
 #include <rtems/score/threadqimpl.h>
-#include <rtems/score/chainimpl.h>
-#include <rtems/score/threadimpl.h>
 
 Thread_Control *_Thread_queue_First_locked(
   Thread_queue_Control *the_thread_queue
 )
 {
-  Thread_Control *thread;
-
-  thread = NULL;
-
-  if ( the_thread_queue->discipline == THREAD_QUEUE_DISCIPLINE_FIFO ) {
-    if ( !_Chain_Is_empty( &the_thread_queue->Queues.Fifo ) )
-      thread = (Thread_Control *) _Chain_First(&the_thread_queue->Queues.Fifo);
-  } else { /* must be THREAD_QUEUE_DISCIPLINE_PRIORITY */
-    RBTree_Node *first;
-
-    first = _RBTree_First( &the_thread_queue->Queues.Priority, RBT_LEFT );
-    if ( first )
-      thread = THREAD_RBTREE_NODE_TO_THREAD( first );
-  }
-
-  return thread;
+  return ( *the_thread_queue->operations->first )( the_thread_queue );
 }
 
 Thread_Control *_Thread_queue_First(
diff --git a/cpukit/score/src/threadqops.c b/cpukit/score/src/threadqops.c
index 561480130a..9958ed667c 100644
--- a/cpukit/score/src/threadqops.c
+++ b/cpukit/score/src/threadqops.c
@@ -17,40 +17,167 @@
 #endif
 
 #include <rtems/score/threadimpl.h>
+#include <rtems/score/chainimpl.h>
 #include <rtems/score/rbtreeimpl.h>
 
 static void _Thread_queue_Do_nothing_priority_change(
   Thread_Control       *the_thread,
   Priority_Control      new_priority,
-  Thread_queue_Control *queue
+  Thread_queue_Control *the_thread_queue
 )
 {
   /* Do nothing */
 }
 
+static void _Thread_queue_Do_nothing_extract(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
+)
+{
+  /* Do nothing */
+}
+
+static void _Thread_queue_FIFO_initialize(
+  Thread_queue_Control *the_thread_queue
+)
+{
+  _Chain_Initialize_empty( &the_thread_queue->Queues.Fifo );
+}
+
+static void _Thread_queue_FIFO_enqueue(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
+)
+{
+  _Chain_Append_unprotected(
+    &the_thread_queue->Queues.Fifo,
+    &the_thread->Wait.Node.Chain
+  );
+}
+
+static Thread_Control *_Thread_queue_FIFO_dequeue(
+  Thread_queue_Control *the_thread_queue
+)
+{
+  Chain_Control *fifo = &the_thread_queue->Queues.Fifo;
+
+  return _Chain_Is_empty( fifo ) ?
+    NULL : THREAD_CHAIN_NODE_TO_THREAD( _Chain_Get_first_unprotected( fifo ) );
+}
+
+static void _Thread_queue_FIFO_extract(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
+)
+{
+  _Chain_Extract_unprotected( &the_thread->Wait.Node.Chain );
+}
+
+static Thread_Control *_Thread_queue_FIFO_first(
+  Thread_queue_Control *the_thread_queue
+)
+{
+  Chain_Control *fifo = &the_thread_queue->Queues.Fifo;
+
+  return _Chain_Is_empty( fifo ) ?
+    NULL : THREAD_CHAIN_NODE_TO_THREAD( _Chain_First( fifo ) );
+}
+
 static void _Thread_queue_Priority_priority_change(
   Thread_Control       *the_thread,
   Priority_Control      new_priority,
-  Thread_queue_Control *queue
+  Thread_queue_Control *the_thread_queue
+)
+{
+  _RBTree_Extract(
+    &the_thread_queue->Queues.Priority,
+    &the_thread->Wait.Node.RBTree
+  );
+  _RBTree_Insert(
+    &the_thread_queue->Queues.Priority,
+    &the_thread->Wait.Node.RBTree,
+    _Thread_queue_Compare_priority,
+    false
+  );
+}
+
+static void _Thread_queue_Priority_initialize(
+  Thread_queue_Control *the_thread_queue
+)
+{
+  _RBTree_Initialize_empty( &the_thread_queue->Queues.Priority );
+}
+
+static void _Thread_queue_Priority_enqueue(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
 )
 {
-  _RBTree_Extract( &queue->Queues.Priority, &the_thread->RBNode );
   _RBTree_Insert(
-    &queue->Queues.Priority,
-    &the_thread->RBNode,
+    &the_thread_queue->Queues.Priority,
+    &the_thread->Wait.Node.RBTree,
     _Thread_queue_Compare_priority,
     false
   );
 }
 
+static Thread_Control *_Thread_queue_Priority_dequeue(
+  Thread_queue_Control *the_thread_queue
+)
+{
+  RBTree_Node *first;
+
+  first = _RBTree_Get( &the_thread_queue->Queues.Priority, RBT_LEFT );
+
+  return first != NULL ? THREAD_RBTREE_NODE_TO_THREAD( first ) : NULL;
+}
+
+static void _Thread_queue_Priority_extract(
+  Thread_queue_Control *the_thread_queue,
+  Thread_Control       *the_thread
+)
+{
+  _RBTree_Extract(
+    &the_thread_queue->Queues.Priority,
+    &the_thread->Wait.Node.RBTree
+  );
+}
+
+static Thread_Control *_Thread_queue_Priority_first(
+  Thread_queue_Control *the_thread_queue
+)
+{
+  RBTree_Node *first;
+
+  first = _RBTree_First( &the_thread_queue->Queues.Priority, RBT_LEFT );
+
+  return first != NULL ? THREAD_RBTREE_NODE_TO_THREAD( first ) : NULL;
+}
+
 const Thread_queue_Operations _Thread_queue_Operations_default = {
-  .priority_change = _Thread_queue_Do_nothing_priority_change
+  .priority_change = _Thread_queue_Do_nothing_priority_change,
+  .extract = _Thread_queue_Do_nothing_extract
+  /*
+   * The default operations are only used in _Thread_Change_priority() and
+   * _Thread_Timeout() and don't have a thread queue associated with them, so
+   * the enqueue and first operations are superfluous.
+   */
 };
 
 const Thread_queue_Operations _Thread_queue_Operations_FIFO = {
-  .priority_change = _Thread_queue_Do_nothing_priority_change
+  .priority_change = _Thread_queue_Do_nothing_priority_change,
+  .initialize = _Thread_queue_FIFO_initialize,
+  .enqueue = _Thread_queue_FIFO_enqueue,
+  .dequeue = _Thread_queue_FIFO_dequeue,
+  .extract = _Thread_queue_FIFO_extract,
+  .first = _Thread_queue_FIFO_first
 };
 
 const Thread_queue_Operations _Thread_queue_Operations_priority = {
-  .priority_change = _Thread_queue_Priority_priority_change
+  .priority_change = _Thread_queue_Priority_priority_change,
+  .initialize = _Thread_queue_Priority_initialize,
+  .enqueue = _Thread_queue_Priority_enqueue,
+  .dequeue = _Thread_queue_Priority_dequeue,
+  .extract = _Thread_queue_Priority_extract,
+  .first = _Thread_queue_Priority_first
 };
diff --git a/cpukit/score/src/threadtimeout.c b/cpukit/score/src/threadtimeout.c
index b6ce2d7362..300beb5219 100644
--- a/cpukit/score/src/threadtimeout.c
+++ b/cpukit/score/src/threadtimeout.c
@@ -24,6 +24,12 @@
 static void _Thread_Do_timeout( Thread_Control *the_thread )
 {
   the_thread->Wait.return_code = the_thread->Wait.timeout_code;
+  ( *the_thread->Wait.operations->extract )(
+    the_thread->Wait.queue,
+    the_thread
+  );
+  _Thread_Wait_set_queue( the_thread, NULL );
+  _Thread_Wait_restore_default_operations( the_thread );
   _Thread_Lock_restore_default( the_thread );
 }