[PATCH 05/15] score: Use red-black tree for active MP proxies

Sebastian Huber sebastian.huber at embedded-brains.de
Tue Apr 5 13:09:50 UTC 2016


Update #2555.
---
 cpukit/score/include/rtems/score/thread.h   |   6 +-
 cpukit/score/include/rtems/score/threadmp.h |  29 +----
 cpukit/score/src/threadmp.c                 | 162 +++++++++++++++++-----------
 testsuites/sptests/spsize/size.c            |   5 -
 4 files changed, 106 insertions(+), 96 deletions(-)

diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h
index 7bb65e4..d9f1eb2 100644
--- a/cpukit/score/include/rtems/score/thread.h
+++ b/cpukit/score/include/rtems/score/thread.h
@@ -431,8 +431,10 @@ typedef struct {
    */
   Objects_Id               thread_queue_id;
 
-  /** This field is used to manage the set of proxies in the system. */
-  Chain_Node               Active;
+  /**
+   * @brief This field is used to manage the set of active proxies in the system.
+   */
+  RBTree_Node              Active;
 
   /**
    * @brief Provide thread queue heads for this thread proxy.
diff --git a/cpukit/score/include/rtems/score/threadmp.h b/cpukit/score/include/rtems/score/threadmp.h
index d287780..5dc5c7e 100644
--- a/cpukit/score/include/rtems/score/threadmp.h
+++ b/cpukit/score/include/rtems/score/threadmp.h
@@ -69,27 +69,13 @@ Thread_Control *_Thread_MP_Allocate_proxy (
  *  id from the active chain of proxy control blocks.
  *
  *  This function removes the proxy control block for the specified
- *  id from the active chain of proxy control blocks.
+ *  id from the active red-black tree of proxy control blocks.
  */
 Thread_Control *_Thread_MP_Find_proxy (
   Objects_Id the_id
 );
 
 /**
- *  @brief Manage the active set MP proxies.
- *
- * The following chain is used to manage the active set proxies.
- */
-extern Chain_Control _Thread_MP_Active_proxies;
-
-/**
- *  @brief Manage the inactive set of MP proxies.
- *
- * The following chain is used to manage the inactive set of proxies.
- */
-extern Chain_Control _Thread_MP_Inactive_proxies;
-
-/**
  * This function returns true if the thread in question is the
  * multiprocessing receive thread.
  *
@@ -103,19 +89,8 @@ extern Chain_Control _Thread_MP_Inactive_proxies;
  * This routine frees a proxy control block to the
  * inactive chain of free proxy control blocks.
  */
+void _Thread_MP_Free_proxy( Thread_Control *the_thread );
 
-RTEMS_INLINE_ROUTINE void _Thread_MP_Free_proxy (
-  Thread_Control *the_thread
-)
-{
-  Thread_Proxy_control *the_proxy;
-
-  the_proxy = (Thread_Proxy_control *) the_thread;
-
-  _Chain_Extract( &the_proxy->Active );
-
-  _Chain_Append( &_Thread_MP_Inactive_proxies, &the_thread->Object.Node );
-}
 
 /**@}*/
 
diff --git a/cpukit/score/src/threadmp.c b/cpukit/score/src/threadmp.c
index 8ba4d49..5dd3e88 100644
--- a/cpukit/score/src/threadmp.c
+++ b/cpukit/score/src/threadmp.c
@@ -19,14 +19,26 @@
 #endif
 
 #include <rtems/score/threadimpl.h>
-#include <rtems/score/isrlevel.h>
+#include <rtems/score/isrlock.h>
 #include <rtems/score/wkspace.h>
 
 #include <string.h>
 
-Chain_Control _Thread_MP_Active_proxies;
+static RBTREE_DEFINE_EMPTY( _Thread_MP_Active_proxies );
 
-Chain_Control _Thread_MP_Inactive_proxies;
+static CHAIN_DEFINE_EMPTY( _Thread_MP_Inactive_proxies );
+
+ISR_LOCK_DEFINE( static, _Thread_MP_Proxies_lock, "Thread MP Proxies" )
+
+static void _Thread_MP_Proxies_acquire( ISR_lock_Context *lock_context )
+{
+  _ISR_lock_ISR_disable_and_acquire( &_Thread_MP_Proxies_lock, lock_context );
+}
+
+static void _Thread_MP_Proxies_release( ISR_lock_Context *lock_context )
+{
+  _ISR_lock_Release_and_ISR_enable( &_Thread_MP_Proxies_lock, lock_context );
+}
 
 void _Thread_MP_Handler_initialization (
   uint32_t    maximum_proxies
@@ -37,10 +49,7 @@ void _Thread_MP_Handler_initialization (
   char     *proxies;
   uint32_t  i;
 
-  _Chain_Initialize_empty( &_Thread_MP_Active_proxies );
-
   if ( maximum_proxies == 0 ) {
-    _Chain_Initialize_empty( &_Thread_MP_Inactive_proxies );
     return;
   }
 
@@ -69,30 +78,67 @@ void _Thread_MP_Handler_initialization (
   }
 }
 
+#define THREAD_MP_PROXY_OF_ACTIVE_NODE( the_node ) \
+  RTEMS_CONTAINER_OF( the_node, Thread_Proxy_control, Active )
+
+static bool _Thread_MP_Proxy_equal(
+  const void        *left,
+  const RBTree_Node *right
+)
+{
+  const Objects_Id           *the_left;
+  const Thread_Proxy_control *the_right;
+
+  the_left = left;
+  the_right = THREAD_MP_PROXY_OF_ACTIVE_NODE( right );
+
+  return *the_left == the_right->Object.id;
+}
+
+static bool _Thread_MP_Proxy_less(
+  const void        *left,
+  const RBTree_Node *right
+)
+{
+  const Objects_Id           *the_left;
+  const Thread_Proxy_control *the_right;
+
+  the_left = left;
+  the_right = THREAD_MP_PROXY_OF_ACTIVE_NODE( right );
+
+  return *the_left < the_right->Object.id;
+}
+
+static void *_Thread_MP_Proxy_adjust( RBTree_Node *node )
+{
+  return THREAD_MP_PROXY_OF_ACTIVE_NODE( node );
+}
+
 Thread_Control *_Thread_MP_Allocate_proxy (
   States_Control  the_state
 )
 {
-  Thread_Control       *the_thread;
   Thread_Proxy_control *the_proxy;
+  ISR_lock_Context      lock_context;
 
-  the_thread = (Thread_Control *)_Chain_Get( &_Thread_MP_Inactive_proxies );
+  _Thread_MP_Proxies_acquire( &lock_context );
 
-  if ( !_Thread_Is_null( the_thread ) ) {
-    Thread_Control *executing;
+  the_proxy = (Thread_Proxy_control *)
+    _Chain_Get_unprotected( &_Thread_MP_Inactive_proxies );
+  if ( the_proxy != NULL ) {
+    Thread_Control   *executing;
+    MP_packet_Prefix *receive_packet;
+    Objects_Id        source_tid;
 
     executing = _Thread_Executing;
-    the_proxy = (Thread_Proxy_control *) the_thread;
+    receive_packet = _MPCI_Receive_server_tcb->receive_packet;
+    source_tid = receive_packet->source_tid;
 
     executing->Wait.return_code = THREAD_STATUS_PROXY_BLOCKING;
 
-    the_proxy->receive_packet = _MPCI_Receive_server_tcb->receive_packet;
-
-    the_proxy->Object.id = _MPCI_Receive_server_tcb->receive_packet->source_tid;
-
-    the_proxy->current_priority =
-      _MPCI_Receive_server_tcb->receive_packet->source_priority;
-
+    the_proxy->receive_packet = receive_packet;
+    the_proxy->Object.id = source_tid;
+    the_proxy->current_priority = receive_packet->source_priority;
     the_proxy->current_state = _States_Set( STATES_DORMANT, the_state );
 
     the_proxy->Wait.count                   = executing->Wait.count;
@@ -104,11 +150,20 @@ Thread_Control *_Thread_MP_Allocate_proxy (
 
     the_proxy->thread_queue_callout = _Thread_queue_MP_callout_do_nothing;
 
-    _Chain_Append( &_Thread_MP_Active_proxies, &the_proxy->Active );
+    _RBTree_Insert_inline(
+      &_Thread_MP_Active_proxies,
+      &the_proxy->Active,
+      &source_tid,
+      _Thread_MP_Proxy_less
+    );
+
+    _Thread_MP_Proxies_release( &lock_context );
 
-    return the_thread;
+    return (Thread_Control *) the_proxy;
   }
 
+  _Thread_MP_Proxies_release( &lock_context );
+
   _Terminate(
     INTERNAL_ERROR_CORE,
     true,
@@ -123,59 +178,42 @@ Thread_Control *_Thread_MP_Allocate_proxy (
   return NULL;
 }
 
-/*
- *  The following macro provides the offset of the Active element
- *  in the Thread_Proxy_control structure.  This is the logical
- *  equivalent of the POSITION attribute in Ada.
- */
-
-#define _Thread_MP_Proxy_Active_offset \
-     ((uint32_t)&(((Thread_Proxy_control *)0))->Active)
-
 Thread_Control *_Thread_MP_Find_proxy (
   Objects_Id  the_id
 )
 {
+  Thread_Proxy_control *the_proxy;
+  ISR_lock_Context      lock_context;
 
-  Chain_Node           *proxy_node;
-  Thread_Control       *the_thread;
-  ISR_Level             level;
-
-restart:
-
-  _ISR_Disable( level );
+  _Thread_MP_Proxies_acquire( &lock_context );
 
-    for (  proxy_node = _Chain_First( &_Thread_MP_Active_proxies );
-           !_Chain_Is_tail( &_Thread_MP_Active_proxies, proxy_node ) ;
-        ) {
+  the_proxy = _RBTree_Find_inline(
+    &_Thread_MP_Active_proxies,
+    &the_id,
+    _Thread_MP_Proxy_equal,
+    _Thread_MP_Proxy_less,
+    _Thread_MP_Proxy_adjust
+  );
 
-      the_thread = (Thread_Control *) _Addresses_Subtract_offset(
-                     proxy_node,
-                     _Thread_MP_Proxy_Active_offset
-                   );
+  _Thread_MP_Proxies_release( &lock_context );
 
-      if ( _Objects_Are_ids_equal( the_thread->Object.id, the_id ) ) {
-        _ISR_Enable( level );
-        return the_thread;
-      }
+  return (Thread_Control *) the_proxy;
+}
 
-      _ISR_Flash( level );
+void _Thread_MP_Free_proxy( Thread_Control *the_thread )
+{
+  Thread_Proxy_control *the_proxy;
+  ISR_lock_Context      lock_context;
 
-      proxy_node = _Chain_Next( proxy_node );
+  the_proxy = (Thread_Proxy_control *) the_thread;
 
-      /*
-       *  A proxy which is only dormant is not in a blocking state.
-       *  Therefore, we are looking at proxy which has been moved from
-       *  active to inactive chain (by an ISR) and need to restart
-       *  the search.
-       */
+  _Thread_MP_Proxies_acquire( &lock_context );
 
-      if ( _States_Is_only_dormant( the_thread->current_state ) ) {
-        _ISR_Enable( level );
-        goto restart;
-      }
-    }
+  _RBTree_Extract( &_Thread_MP_Active_proxies, &the_proxy->Active );
+  _Chain_Append_unprotected(
+    &_Thread_MP_Inactive_proxies,
+    &the_proxy->Object.Node
+  );
 
-  _ISR_Enable( level );
-  return NULL;
+  _Thread_MP_Proxies_release( &lock_context );
 }
diff --git a/testsuites/sptests/spsize/size.c b/testsuites/sptests/spsize/size.c
index e19ca99..251ed36 100644
--- a/testsuites/sptests/spsize/size.c
+++ b/testsuites/sptests/spsize/size.c
@@ -375,11 +375,6 @@ uninitialized =
 #endif
                 (sizeof _Thread_Internal_information)     +
 
-#if defined(RTEMS_MULTIPROCESSING)
-/*threadmp.h*/  (sizeof _Thread_MP_Active_proxies)        +
-                (sizeof _Thread_MP_Inactive_proxies)      +
-#endif
-
 /*threadq.h*/
 
 /*timerimpl.h*/ (sizeof _Timer_Information)               +
-- 
1.8.4.5



More information about the devel mailing list