[PATCH 1/2] posix: Reimplement POSIX Key manager to use a red-black tree.

Gedare Bloom gedare at rtems.org
Sat Feb 23 14:38:26 UTC 2013


From: Zhongwei Yao <ashi08104 at gmail.com>

The POSIX Key manager is reimplemented with a red-black tree to store
the keys and values. This code was contributed as part of GSOC 2012.
---
 cpukit/posix/include/rtems/posix/key.h       |   54 ++++++++++++++++-----
 cpukit/posix/include/rtems/posix/threadsup.h |   10 ++++
 cpukit/posix/inline/rtems/posix/key.inl      |    2 +-
 cpukit/posix/src/key.c                       |   59 ++++++++++++++++++++++-
 cpukit/posix/src/keycreate.c                 |   52 +-------------------
 cpukit/posix/src/keydelete.c                 |    3 +-
 cpukit/posix/src/keyfreememory.c             |   35 ++++++++++++-
 cpukit/posix/src/keygetspecific.c            |   20 +++++---
 cpukit/posix/src/keyrundestructors.c         |   67 +++++++++++++++----------
 cpukit/posix/src/keysetspecific.c            |   34 ++++++++++---
 cpukit/posix/src/pthread.c                   |    3 +
 cpukit/sapi/src/posixapi.c                   |    2 +-
 12 files changed, 229 insertions(+), 112 deletions(-)

diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
index 0bb1dbe..f045dad 100644
--- a/cpukit/posix/include/rtems/posix/key.h
+++ b/cpukit/posix/include/rtems/posix/key.h
@@ -8,6 +8,7 @@
  */
 
 /*
+ *  Copyright (c) 2012 Zhongwei Yao.
  *  COPYRIGHT (c) 1989-2011.
  *  On-Line Applications Research Corporation (OAR).
  *
@@ -20,6 +21,8 @@
 #define _RTEMS_POSIX_KEY_H
 
 #include <rtems/score/object.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/chain.h>
 
 /**
  * @defgroup POSIX_KEY POSIX Key
@@ -34,32 +37,57 @@ extern "C" {
 #endif
 
 /**
- * This is the data Structure used to manage a POSIX key.
- *
- * NOTE: The Values is a table indexed by the index portion of the
- *       ID of the currently executing thread.
+ * @brief The rbtree node used to manage a POSIX key and value.
+ */
+typedef struct {
+  /** This field is the chain node structure. */
+  Chain_Node ch_node;
+  /** This field is the rbtree node structure. */
+  RBTree_Node rb_node;
+  /** This field is the POSIX key used as an rbtree key */
+  pthread_key_t key;
+  /** This field is the Thread id also used as an rbtree key */
+  Objects_Id thread_id;
+  /** This field points to the POSIX key value of specific thread */
+  void *value;
+ }  POSIX_Keys_Rbtree_node;
+
+/**
+ * @brief The data structure used to manage a POSIX key.
  */
 typedef struct {
    /** This field is the Object control structure. */
-   Objects_Control     Object;
-   /** This field points to the optional destructor method. */
-   void              (*destructor)( void * );
-   /** This field points to the values per thread. */
-   void              **Values[ OBJECTS_APIS_LAST + 1 ];
-}  POSIX_Keys_Control;
+   Objects_Control     object;
+   /** This field is the data destructor. */
+   void (*destructor) (void *);
+ }  POSIX_Keys_Control;
 
 /**
- * The following defines the information control block used to manage
- * this class of objects.
+ * @brief The information control block used to manage this class of objects.
  */
 POSIX_EXTERN Objects_Information  _POSIX_Keys_Information;
 
 /**
+ * @brief The rbtree control block used to manage all key values
+ */
+POSIX_EXTERN RBTree_Control _POSIX_Keys_Rbtree;
+
+/**
  * @brief POSIX keys manager initialization.
  *
  * This routine performs the initialization necessary for this manager.
  */
-void _POSIX_Key_Manager_initialization(void);
+void _POSIX_Keys_Manager_initialization(void);
+
+/**
+ * @brief POSIX keys Red-Black tree node comparison.
+ *
+ * This routine compares the rbtree node
+ */
+int _POSIX_Keys_Rbtree_compare_function(
+  const RBTree_Node *node1,
+  const RBTree_Node *node2
+);
 
 /**
  * @brief Create thread-specific data POSIX key.
diff --git a/cpukit/posix/include/rtems/posix/threadsup.h b/cpukit/posix/include/rtems/posix/threadsup.h
index 80f64dc..d746ea8 100644
--- a/cpukit/posix/include/rtems/posix/threadsup.h
+++ b/cpukit/posix/include/rtems/posix/threadsup.h
@@ -21,6 +21,7 @@
 #include <sys/signal.h>
 #include <rtems/score/coresem.h>
 #include <rtems/score/tqdata.h>
+#include <rtems/score/chain.h>
 
 /**
  *  @defgroup POSIX_THREAD POSIX Thread API Extension
@@ -79,6 +80,15 @@ typedef struct {
   /** This is the set of cancelation handlers. */
   Chain_Control           Cancellation_Handlers;
 
+  /**
+   * This is the thread key value chain's control, which is used
+   * to track all key value for specific thread, and when thread
+   * exits, we can remove all key value for specific thread by
+   * iterating this chain, or we have to search a whole rbtree,
+   * which is inefficient.
+   */
+  Chain_Control           Key_Chain;
+
 } POSIX_API_Control;
 
 /**
diff --git a/cpukit/posix/inline/rtems/posix/key.inl b/cpukit/posix/inline/rtems/posix/key.inl
index ce5601b..9469580 100644
--- a/cpukit/posix/inline/rtems/posix/key.inl
+++ b/cpukit/posix/inline/rtems/posix/key.inl
@@ -45,7 +45,7 @@ RTEMS_INLINE_ROUTINE void _POSIX_Keys_Free (
   POSIX_Keys_Control *the_key
 )
 {
-  _Objects_Free( &_POSIX_Keys_Information, &the_key->Object );
+  _Objects_Free( &_POSIX_Keys_Information, &the_key->object );
 }
  
 /**
diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
index 6eace26..82c11af 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -29,6 +29,57 @@
 #include <rtems/score/thread.h>
 #include <rtems/score/wkspace.h>
 #include <rtems/posix/key.h>
+#include <rtems/score/rbtree.h>
+
+/*
+ * _POSIX_Keys_Rbtree_compare_function
+ *
+ * DESCRIPTION:
+ * This routine compares the rbtree node
+ * by comparing POSIX key first and comparing thread id second.
+ * And if either of the input nodes's thread_id member is 0, then
+ * it will only compare the pthread_key_t member. That is when we
+ * pass thread_id = 0 node as a search node, the search is done only
+ * by pthread_key_t.
+ *
+ * Input parameters: two rbtree node
+ *
+ * Output parameters: return positive if first node
+ * has higher key than second, negative if lower, 0 if equal,
+ * and for all the thread id is unique, then return 0 is impossible
+ */
+
+int _POSIX_Keys_Rbtree_compare_function(
+  const RBTree_Node *node1,
+  const RBTree_Node *node2
+)
+{
+  pthread_key_t key1 = _RBTree_Container_of(node1,
+					    POSIX_Keys_Rbtree_node,
+					    rb_node)->key;
+  pthread_key_t key2 = _RBTree_Container_of(node2,
+					    POSIX_Keys_Rbtree_node,
+					    rb_node)->key;
+
+  Objects_Id thread_id1 = _RBTree_Container_of(node1,
+					       POSIX_Keys_Rbtree_node,
+					       rb_node)->thread_id;
+  Objects_Id thread_id2 = _RBTree_Container_of(node2,
+					       POSIX_Keys_Rbtree_node,
+					       rb_node)->thread_id;
+
+  int diff = key1 - key2;
+  if ( diff )
+    return diff;
+  /**
+   * if thread_id1 or thread_id2 equals to 0, only key1 and key2 is valued.
+   * it enables us search node only by pthread_key_t type key.
+   */
+  if ( thread_id1 && thread_id2 )
+    return thread_id1 - thread_id2;
+  return 0;
+}
+
 
 /*
  *  _POSIX_Key_Manager_initialization
@@ -42,7 +93,7 @@
  *  Output parameters:  NONE
  */
 
-void _POSIX_Key_Manager_initialization(void)
+void _POSIX_Keys_Manager_initialization(void)
 {
   _Objects_Initialize_information(
     &_POSIX_Keys_Information,   /* object information table */
@@ -60,4 +111,10 @@ void _POSIX_Key_Manager_initialization(void)
     NULL                        /* Proxy extraction support callout */
 #endif
   );
+
+  _RBTree_Initialize_empty(
+    &_POSIX_Keys_Rbtree,
+    _POSIX_Keys_Rbtree_compare_function,
+    true
+  );
 }
diff --git a/cpukit/posix/src/keycreate.c b/cpukit/posix/src/keycreate.c
index b41b590..09778c3 100644
--- a/cpukit/posix/src/keycreate.c
+++ b/cpukit/posix/src/keycreate.c
@@ -37,10 +37,6 @@ int pthread_key_create(
 )
 {
   POSIX_Keys_Control  *the_key;
-  void                *table;
-  uint32_t             the_api;
-  uint32_t             bytes_to_allocate;
-
 
   _Thread_Disable_dispatch();
 
@@ -52,52 +48,8 @@ int pthread_key_create(
   }
 
   the_key->destructor = destructor;
-
-  /*
-   *  This is a bit more complex than one might initially expect because
-   *  APIs are optional.
-   *
-   *  NOTE: Currently RTEMS Classic API tasks are always enabled.
-   */
-  for ( the_api = 1; the_api <= OBJECTS_APIS_LAST; the_api++ ) {
-    the_key->Values[ the_api ] = NULL;
-
-    #if defined(RTEMS_DEBUG)
-      /*
-       *  Since the removal of ITRON, this cannot occur.
-       */
-      if ( !_Objects_Information_table[ the_api ] )
-	continue;
-
-      /*
-       * Currently all managers are installed if the API is installed.
-       * This would be a horrible implementation error.
-       */
-      if (_Objects_Information_table[ the_api ][ 1 ] == NULL )
-	_Internal_error_Occurred(
-	  INTERNAL_ERROR_CORE,
-	  true,
-	  INTERNAL_ERROR_IMPLEMENTATION_KEY_CREATE_INCONSISTENCY
-	);
-    #endif
-
-    bytes_to_allocate = sizeof( void * ) *
-      (_Objects_Information_table[ the_api ][ 1 ]->maximum + 1);
-    table = _Workspace_Allocate( bytes_to_allocate );
-    if ( !table ) {
-      _POSIX_Keys_Free_memory( the_key );
-
-      _POSIX_Keys_Free( the_key );
-      _Thread_Enable_dispatch();
-      return ENOMEM;
-    }
-
-    the_key->Values[ the_api ] = table;
-    memset( table, '\0', bytes_to_allocate );
-  }
-
-  _Objects_Open_u32( &_POSIX_Keys_Information, &the_key->Object, 0 );
-  *key = the_key->Object.id;
+  _Objects_Open_u32( &_POSIX_Keys_Information, &the_key->object, 0 );
+  *key = the_key->object.id;
   _Thread_Enable_dispatch();
   return 0;
 }
diff --git a/cpukit/posix/src/keydelete.c b/cpukit/posix/src/keydelete.c
index 5ef6261..3f594bd 100644
--- a/cpukit/posix/src/keydelete.c
+++ b/cpukit/posix/src/keydelete.c
@@ -42,8 +42,6 @@ int pthread_key_delete(
   switch ( location ) {
 
     case OBJECTS_LOCAL:
-      _Objects_Close( &_POSIX_Keys_Information, &the_key->Object );
-
       _POSIX_Keys_Free_memory( the_key );
 
       /*
@@ -51,6 +49,7 @@ int pthread_key_delete(
        *         of the application to free the memory.
        */
       _POSIX_Keys_Free( the_key );
+      _Objects_Close( &_POSIX_Keys_Information, &the_key->object );
       _Thread_Enable_dispatch();
       return 0;
 
diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
index f71af4f..e01e6e9 100644
--- a/cpukit/posix/src/keyfreememory.c
+++ b/cpukit/posix/src/keyfreememory.c
@@ -21,14 +21,43 @@
 #include <rtems/system.h>
 #include <rtems/score/thread.h>
 #include <rtems/score/wkspace.h>
+#include <rtems/score/rbtree.h>
 #include <rtems/posix/key.h>
 
 void _POSIX_Keys_Free_memory(
   POSIX_Keys_Control *the_key
 )
 {
-  uint32_t            the_api;
+  POSIX_Keys_Rbtree_node search_node;
+  POSIX_Keys_Rbtree_node *p;
+  RBTree_Node *iter, *next;
 
-  for ( the_api = 1; the_api <= OBJECTS_APIS_LAST; the_api++ )
-    _Workspace_Free( the_key->Values[ the_api ] );
+  search_node.key = the_key->object.id;
+  search_node.thread_id = 0;
+  iter = _RBTree_Find_unprotected( &_POSIX_Keys_Rbtree, &search_node.rb_node);
+  if ( !iter )
+    return;
+  /**
+   * find the smallest thread_id node in the rbtree.
+   */
+  next = _RBTree_Next_unprotected( iter, RBT_LEFT );
+  p = _RBTree_Container_of( next, POSIX_Keys_Rbtree_node, rb_node );
+  while ( p->key == the_key->object.id) {
+    iter = next;
+    next = _RBTree_Next_unprotected( iter, RBT_LEFT );
+    p = _RBTree_Container_of( next, POSIX_Keys_Rbtree_node, rb_node );
+  }
+
+  /**
+   * delete all nodes belongs to the_key from the rbtree and chain.
+   */
+  p = _RBTree_Container_of( iter, POSIX_Keys_Rbtree_node, rb_node );
+  while ( p->key == the_key->object.id ) {
+    next = _RBTree_Next_unprotected( iter, RBT_RIGHT );
+    _RBTree_Extract_unprotected( &_POSIX_Keys_Rbtree, iter );
+    _Chain_Extract_unprotected( &p->ch_node );
+    _Workspace_Free( p );
+    iter = next;
+    p = _RBTree_Container_of( iter, POSIX_Keys_Rbtree_node, rb_node );
+  }
 }
diff --git a/cpukit/posix/src/keygetspecific.c b/cpukit/posix/src/keygetspecific.c
index debad83..39c0fcc 100644
--- a/cpukit/posix/src/keygetspecific.c
+++ b/cpukit/posix/src/keygetspecific.c
@@ -26,6 +26,7 @@
 #include <rtems/system.h>
 #include <rtems/score/thread.h>
 #include <rtems/score/wkspace.h>
+#include <rtems/score/rbtree.h>
 #include <rtems/posix/key.h>
 
 /*
@@ -36,19 +37,24 @@ void *pthread_getspecific(
   pthread_key_t  key
 )
 {
-  register POSIX_Keys_Control *the_key;
-  uint32_t                     api;
-  uint32_t                     index;
   Objects_Locations            location;
+  POSIX_Keys_Rbtree_node       search_node;
+  RBTree_Node                 *p;
   void                        *key_data;
 
-  the_key = _POSIX_Keys_Get( key, &location );
+  _POSIX_Keys_Get( key, &location );
   switch ( location ) {
 
     case OBJECTS_LOCAL:
-      api      = _Objects_Get_API( _Thread_Executing->Object.id );
-      index    = _Objects_Get_index( _Thread_Executing->Object.id );
-      key_data = (void *) the_key->Values[ api ][ index ];
+      search_node.key = key;
+      search_node.thread_id = _Thread_Executing->Object.id;
+      p = _RBTree_Find_unprotected( &_POSIX_Keys_Rbtree, &search_node.rb_node);
+      key_data = NULL;
+      if ( p ) {
+        key_data = _RBTree_Container_of( p,
+					 POSIX_Keys_Rbtree_node,
+					 rb_node )->value;
+      }
       _Thread_Enable_dispatch();
       return key_data;
 
diff --git a/cpukit/posix/src/keyrundestructors.c b/cpukit/posix/src/keyrundestructors.c
index 9f48888..db31d2b 100644
--- a/cpukit/posix/src/keyrundestructors.c
+++ b/cpukit/posix/src/keyrundestructors.c
@@ -23,7 +23,10 @@
 #include <rtems/system.h>
 #include <rtems/score/object.h>
 #include <rtems/score/thread.h>
+#include <rtems/score/wkspace.h>
+#include <rtems/score/chain.h>
 #include <rtems/posix/key.h>
+#include <rtems/posix/threadsup.h>
 
 /*
  *  _POSIX_Keys_Run_destructors
@@ -38,36 +41,46 @@ void _POSIX_Keys_Run_destructors(
   Thread_Control *thread
 )
 {
-  Objects_Maximum thread_index = _Objects_Get_index( thread->Object.id );
-  Objects_APIs thread_api = _Objects_Get_API( thread->Object.id );
-  bool done = false;
+  Chain_Control *chain;
+  Chain_Node *iter, *next;
+  void *value;
+  void (*destructor) (void *);
+  POSIX_Keys_Control *the_key;
+  Objects_Locations location;
 
-  /*
-   *  The standard allows one to avoid a potential infinite loop and limit the
-   *  number of iterations.  An infinite loop may happen if destructors set
-   *  thread specific data.  This can be considered dubious.
-   *
-   *  Reference: 17.1.1.2 P1003.1c/Draft 10, p. 163, line 99.
-   */
-  while ( !done ) {
-    Objects_Maximum index = 0;
-    Objects_Maximum max = _POSIX_Keys_Information.maximum;
+  _Thread_Disable_dispatch();
 
-    done = true;
+  chain = &((POSIX_API_Control *)\
+	    thread->API_Extensions[ THREAD_API_POSIX ])->Key_Chain;
+  iter = _Chain_First( chain );
+  while ( !_Chain_Is_tail( chain, iter ) ) {
+    next = _Chain_Next( iter );
+    /**
+     * remove key from rbtree and chain.
+     * here Chain_Node *iter can be convert to POSIX_Keys_Rbtree_node *,
+     * because Chain_Node is the first member of POSIX_Keys_Rbtree_node
+     * structure.
+     */
+    _RBTree_Extract_unprotected( &_POSIX_Keys_Rbtree,
+				 &((POSIX_Keys_Rbtree_node *)iter)->rb_node );
+    _Chain_Extract_unprotected( iter );
 
-    for ( index = 1 ; index <= max ; ++index ) {
-      POSIX_Keys_Control *key = (POSIX_Keys_Control *)
-        _POSIX_Keys_Information.local_table [ index ];
+    /**
+     * run key value's destructor if destructor and value are both non-null.
+     */
+    the_key = _POSIX_Keys_Get( ((POSIX_Keys_Rbtree_node *)iter)->key,
+			       &location);
+    destructor = the_key->destructor;
+    value = ((POSIX_Keys_Rbtree_node *)iter)->value;
+    if ( destructor != NULL && value != NULL )
+      (*destructor)( value );
+    /**
+     * disable dispatch is nested here
+     */
+    _Thread_Enable_dispatch();
 
-      if ( key != NULL && key->destructor != NULL ) {
-        void *value = key->Values [ thread_api ][ thread_index ];
-
-        if ( value != NULL ) {
-          key->Values [ thread_api ][ thread_index ] = NULL;
-          (*key->destructor)( value );
-          done = false;
-        }
-      }
-    }
+    _Workspace_Free( (POSIX_Keys_Rbtree_node *)iter );
+    iter = next;
   }
+  _Thread_Enable_dispatch();
 }
diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
index b25e44c..132061a 100644
--- a/cpukit/posix/src/keysetspecific.c
+++ b/cpukit/posix/src/keysetspecific.c
@@ -26,7 +26,9 @@
 #include <rtems/system.h>
 #include <rtems/score/thread.h>
 #include <rtems/score/wkspace.h>
+#include <rtems/score/rbtree.h>
 #include <rtems/posix/key.h>
+#include <rtems/posix/threadsup.h>
 
 /*
  *  17.1.2 Thread-Specific Data Management, P1003.1c/Draft 10, p. 165
@@ -37,18 +39,36 @@ int pthread_setspecific(
   const void    *value
 )
 {
-  register POSIX_Keys_Control *the_key;
-  uint32_t                     api;
-  uint32_t                     index;
   Objects_Locations            location;
+  POSIX_Keys_Rbtree_node      *rb_node;
+  POSIX_API_Control           *api;
 
-  the_key = _POSIX_Keys_Get( key, &location );
+  /** _POSIX_Keys_Get() would call _Thread_Disable_dispatch() implicitly*/
+  _POSIX_Keys_Get( key, &location );
   switch ( location ) {
 
     case OBJECTS_LOCAL:
-      api   = _Objects_Get_API( _Thread_Executing->Object.id );
-      index = _Objects_Get_index( _Thread_Executing->Object.id );
-      the_key->Values[ api ][ index ] = (void *) value;
+      rb_node = _Workspace_Allocate( sizeof( POSIX_Keys_Rbtree_node ) );
+      if ( !rb_node ) {
+        _Thread_Enable_dispatch();
+        return ENOMEM;
+      }
+
+      rb_node->key = key;
+      rb_node->thread_id = _Thread_Executing->Object.id;
+      rb_node->value = value;
+      if (_RBTree_Insert_unprotected( &_POSIX_Keys_Rbtree,
+				      &(rb_node->rb_node) ) ) {
+          _Workspace_Free( rb_node );
+          _Thread_Enable_dispatch();
+          return EAGAIN;
+        }
+
+      /** append rb_node to the thread API extension's chain */
+      api = (POSIX_API_Control *)\
+	(_Thread_Executing->API_Extensions[THREAD_API_POSIX]);
+      _Chain_Append_unprotected( &api->Key_Chain, &rb_node->ch_node );
+
       _Thread_Enable_dispatch();
       return 0;
 
diff --git a/cpukit/posix/src/pthread.c b/cpukit/posix/src/pthread.c
index 873449a..0ea44f1 100644
--- a/cpukit/posix/src/pthread.c
+++ b/cpukit/posix/src/pthread.c
@@ -234,6 +234,9 @@ static bool _POSIX_Threads_Create_extension(
     created
   );
 
+  /** initialize thread's key vaule node chain */
+  _Chain_Initialize_empty( &api->Key_Chain );
+
   return true;
 }
 
diff --git a/cpukit/sapi/src/posixapi.c b/cpukit/sapi/src/posixapi.c
index 3f65442..b5e62c2 100644
--- a/cpukit/sapi/src/posixapi.c
+++ b/cpukit/sapi/src/posixapi.c
@@ -64,7 +64,7 @@ void _POSIX_API_Initialize(void)
   _POSIX_signals_Manager_Initialization();
   _POSIX_Threads_Manager_initialization();
   _POSIX_Condition_variables_Manager_initialization();
-  _POSIX_Key_Manager_initialization();
+  _POSIX_Keys_Manager_initialization();
   _POSIX_Mutex_Manager_initialization();
   _POSIX_Message_queue_Manager_initialization();
   _POSIX_Semaphore_Manager_initialization();
-- 
1.7.1




More information about the devel mailing list