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

Gedare Bloom gedare at rtems.org
Wed Mar 13 00:34:47 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/config.h    |    1 +
 cpukit/posix/include/rtems/posix/key.h       |   71 +++++++++++++++-----
 cpukit/posix/include/rtems/posix/threadsup.h |   10 +++
 cpukit/posix/src/key.c                       |   89 +++++++++++++++++++++----
 cpukit/posix/src/keycreate.c                 |   60 ++--------------
 cpukit/posix/src/keydelete.c                 |   13 ++--
 cpukit/posix/src/keyfreememory.c             |   52 ++++++++++++--
 cpukit/posix/src/keygetspecific.c            |   33 ++++++---
 cpukit/posix/src/keyrundestructors.c         |   93 ++++++++++++++++---------
 cpukit/posix/src/keysetspecific.c            |   51 +++++++++++---
 cpukit/posix/src/pthread.c                   |    3 +
 cpukit/sapi/include/confdefs.h               |   35 ++++++++--
 12 files changed, 352 insertions(+), 159 deletions(-)

diff --git a/cpukit/posix/include/rtems/posix/config.h b/cpukit/posix/include/rtems/posix/config.h
index 460ddcb..44cab26 100644
--- a/cpukit/posix/include/rtems/posix/config.h
+++ b/cpukit/posix/include/rtems/posix/config.h
@@ -49,6 +49,7 @@ typedef struct {
   uint32_t                            maximum_mutexes;
   uint32_t                            maximum_condition_variables;
   uint32_t                            maximum_keys;
+  uint32_t                            maximum_key_pairs;
   uint32_t                            maximum_timers;
   uint32_t                            maximum_queued_signals;
   uint32_t                            maximum_message_queues;
diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
index 0bb1dbe..16aea78 100644
--- a/cpukit/posix/include/rtems/posix/key.h
+++ b/cpukit/posix/include/rtems/posix/key.h
@@ -8,18 +8,21 @@
  */
 
 /*
- *  COPYRIGHT (c) 1989-2011.
- *  On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2012 Zhongwei Yao.
+ * COPYRIGHT (c) 1989-2011.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #ifndef _RTEMS_POSIX_KEY_H
 #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,27 +37,53 @@ 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 chain node, which is
+   * used in pre-allocated key node chain.
+   */
+  Chain_Node pre_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;
+   /** 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 This chain is used in _POSIX_Keys_Preallocation, it contains all
+ * pre-allocated RBTree_Nodes.
+ */
+POSIX_EXTERN Chain_Control _POSIX_Keys_Preallocation_chain;
+
+/**
  * @brief POSIX keys manager initialization.
  *
  * This routine performs the initialization necessary for this manager.
@@ -62,6 +91,16 @@ POSIX_EXTERN Objects_Information  _POSIX_Keys_Information;
 void _POSIX_Key_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.
  *
  * This function executes all the destructors associated with the thread's
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/src/key.c b/cpukit/posix/src/key.c
index 6eace26..e86d408 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -6,12 +6,13 @@
  */
 
 /*
- *  COPYRIGHT (c) 1989-2008.
- *  On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2012 Zhongwei Yao.
+ * COPYRIGHT (c) 1989-2008.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -29,19 +30,73 @@
 #include <rtems/score/thread.h>
 #include <rtems/score/wkspace.h>
 #include <rtems/posix/key.h>
+#include <rtems/score/rbtree.h>
+#include <rtems/score/chain.h>
 
-/*
- *  _POSIX_Key_Manager_initialization
- *
- *  DESCRIPTION:
- *
- *  This routine performs the initialization necessary for this manager.
+/**
+ * @brief This routine pre-allocates the memory used for all key data.
+ */
+void _POSIX_Keys_Preallocation(void)
+{
+  POSIX_Keys_Rbtree_node *rb_node;
+  int i;
+
+  _Chain_Initialize_empty( &_POSIX_Keys_Preallocation_chain );
+
+  for ( i = 0; i < Configuration_POSIX_API.maximum_key_pairs; ++i ) {
+    rb_node = _Workspace_Allocate( sizeof( POSIX_Keys_Rbtree_node ) );
+    _Chain_Append( &_POSIX_Keys_Preallocation_chain, &rb_node->pre_ch_node );
+  }
+}
+
+/**
+ * @brief This routine compares the rbtree node by comparing POSIX key first
+ * and comparing thread id second.
  *
- *  Input parameters:   NONE
+ * 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.
  *
- *  Output parameters:  NONE
+ * @param[in] node1 The node to be compared
+ * @param[in] node2 The node to be compared
+ * @retval positive if first node has higher key than second
+ * @retval negative if lower
+ * @retval 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
+)
+{
+  POSIX_Keys_Rbtree_node *n1;
+  POSIX_Keys_Rbtree_node *n2;
+  Objects_Id thread_id1, thread_id2;
+  int diff;
+
+  n1 = _RBTree_Container_of( node1, POSIX_Keys_Rbtree_node, rb_node );
+  n2 = _RBTree_Container_of( node2, POSIX_Keys_Rbtree_node, rb_node );
+
+  diff = n1->key - n2->key;
+  if ( diff )
+    return diff;
+
+  thread_id1 = n1->thread_id;
+  thread_id2 = n2->thread_id;
+
+  /**
+   * 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;
+}
+
+/**
+ * @brief This routine performs the initialization necessary for this manager.
+ */
 void _POSIX_Key_Manager_initialization(void)
 {
   _Objects_Initialize_information(
@@ -60,4 +115,12 @@ void _POSIX_Key_Manager_initialization(void)
     NULL                        /* Proxy extraction support callout */
 #endif
   );
+
+  _RBTree_Initialize_empty(
+      &_POSIX_Keys_Rbtree,
+      _POSIX_Keys_Rbtree_compare_function,
+      true
+  );
+
+  _POSIX_Keys_Preallocation();
 }
diff --git a/cpukit/posix/src/keycreate.c b/cpukit/posix/src/keycreate.c
index b41b590..2e1f319 100644
--- a/cpukit/posix/src/keycreate.c
+++ b/cpukit/posix/src/keycreate.c
@@ -1,17 +1,17 @@
 /**
- *  @file
+ * @file
  *
- *  @brief Thread-Specific Data Key Create
- *  @ingroup POSIXAPI
+ * @brief Thread-Specific Data Key Create
+ * @ingroup POSIXAPI
  */
 
 /*
- *  COPYRIGHT (c) 1989-2010.
- *  On-Line Applications Research Corporation (OAR).
+ * COPYRIGHT (c) 1989-2010.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -52,50 +52,6 @@ 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;
   _Thread_Enable_dispatch();
diff --git a/cpukit/posix/src/keydelete.c b/cpukit/posix/src/keydelete.c
index 5ef6261..0e240da 100644
--- a/cpukit/posix/src/keydelete.c
+++ b/cpukit/posix/src/keydelete.c
@@ -6,12 +6,12 @@
  */
 
 /*
- *  COPYRIGHT (c) 1989-2007.
- *  On-Line Applications Research Corporation (OAR).
+ * COPYRIGHT (c) 1989-2007.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -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..510e572 100644
--- a/cpukit/posix/src/keyfreememory.c
+++ b/cpukit/posix/src/keyfreememory.c
@@ -6,12 +6,13 @@
  */
 
 /*
- *  COPYRIGHT (c) 1989-2010.
- *  On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2012 Zhongwei Yao.
+ * COPYRIGHT (c) 1989-2010.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -21,14 +22,49 @@
 #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 );
+    /**
+     * append the node to pre-allocated POSIX_Keys_Rbtree_node
+     * chain(namely, the POSIX_Keys_Rbtree_node pool
+     */
+    _Chain_Append_unprotected( &_POSIX_Keys_Preallocation_chain,
+                               &p->pre_ch_node );
+    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..6cd3711 100644
--- a/cpukit/posix/src/keygetspecific.c
+++ b/cpukit/posix/src/keygetspecific.c
@@ -6,12 +6,13 @@
  */
 
 /*
- *  COPYRIGHT (c) 1989-2007.
- *  On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2012 Zhongwei Yao.
+ * COPYRIGHT (c) 1989-2007.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -26,6 +27,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 +38,26 @@ 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..4f61702 100644
--- a/cpukit/posix/src/keyrundestructors.c
+++ b/cpukit/posix/src/keyrundestructors.c
@@ -6,14 +6,15 @@
  */
 
 /*
- *  Copyright (c) 2010 embedded brains GmbH.
+ * Copyright (c) 2012 Zhongwei Yao.
+ * Copyright (c) 2010 embedded brains GmbH.
  *
- *  COPYRIGHT (c) 1989-2007.
- *  On-Line Applications Research Corporation (OAR).
+ * COPYRIGHT (c) 1989-2007.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -23,7 +24,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
@@ -33,41 +37,62 @@
  *  NOTE:  This is the routine executed when a thread exits to
  *         run through all the keys and do the destructor action.
  */
-
 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;
-
-  /*
-   *  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;
+  Chain_Control *chain;
+  Chain_Node *iter, *next;
+  void *value;
+  void (*destructor) (void *);
+  POSIX_Keys_Control *the_key;
+  Objects_Locations location;
 
-    done = true;
+  _Thread_Disable_dispatch();
 
-    for ( index = 1 ; index <= max ; ++index ) {
-      POSIX_Keys_Control *key = (POSIX_Keys_Control *)
-        _POSIX_Keys_Information.local_table [ index ];
+  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 );
 
-      if ( key != NULL && key->destructor != NULL ) {
-        void *value = key->Values [ thread_api ][ thread_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 ( value != NULL ) {
-          key->Values [ thread_api ][ thread_index ] = NULL;
-          (*key->destructor)( value );
-          done = false;
-        }
-      }
-    }
+    /**
+     * append the node to pre-allocated POSIX_Keys_Rbtree_node
+     * chain(namely, the POSIX_Keys_Rbtree_node pool
+     */
+    _Chain_Append_unprotected(
+      &_POSIX_Keys_Preallocation_chain,
+      &((POSIX_Keys_Rbtree_node *)iter)->pre_ch_node
+    );
+    iter = next;
   }
+  _Thread_Enable_dispatch();
 }
diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
index b25e44c..de96964 100644
--- a/cpukit/posix/src/keysetspecific.c
+++ b/cpukit/posix/src/keysetspecific.c
@@ -6,12 +6,13 @@
  */
 
 /*
- *  COPYRIGHT (c) 1989-2007.
- *  On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2012 Zhongwei Yao.
+ * COPYRIGHT (c) 1989-2007.
+ * On-Line Applications Research Corporation (OAR).
  *
- *  The license and distribution terms for this file may be
- *  found in the file LICENSE in this distribution or at
- *  http://www.rtems.com/license/LICENSE.
+ * The license and distribution terms for this file may be
+ * found in the file LICENSE in this distribution or at
+ * http://www.rtems.com/license/LICENSE.
  */
 
 #if HAVE_CONFIG_H
@@ -22,11 +23,14 @@
 #include <limits.h>
 #include <pthread.h>
 #include <string.h>
+#include <stddef.h>
 
 #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 +41,41 @@ 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;
+  Chain_Node                  *ch_node;
+  POSIX_API_Control           *api;
 
-  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 );
-      the_key->Values[ api ][ index ] = (void *) value;
+      ch_node = _Chain_Get_unprotected( &_POSIX_Keys_Preallocation_chain );
+      /* there is no _Chain_Container_of in RTEMS Chain API */
+      rb_node = ( POSIX_Keys_Rbtree_node * ) \
+        ( ( uintptr_t )( ch_node ) \
+          - offsetof( POSIX_Keys_Rbtree_node, pre_ch_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) ) ) {
+        _Chain_Append_unprotected( &_POSIX_Keys_Preallocation_chain,
+                                     ch_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/include/confdefs.h b/cpukit/sapi/include/confdefs.h
index cc55e92..2aaf30e 100644
--- a/cpukit/sapi/include/confdefs.h
+++ b/cpukit/sapi/include/confdefs.h
@@ -1709,11 +1709,18 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
 
   #ifndef CONFIGURE_MAXIMUM_POSIX_KEYS
     #define CONFIGURE_MAXIMUM_POSIX_KEYS           0
-    #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys) 0
+    #define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS      0
+    #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys, _key_pairs) 0
   #else
-    #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys) \
+    #ifndef CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS
+      #define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS \
+        CONFIGURE_MAXIMUM_POSIX_KEYS \
+        * (CONFIGURE_MAXIMUM_POSIX_THREADS + CONFIGURE_MAXIMUM_TASKS)
+    #endif
+  #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys, _key_pairs)       \
       (_Configure_Object_RAM(_keys, sizeof(POSIX_Keys_Control) ) \
-        + (_keys) * 3 * _Configure_From_workspace(sizeof(void *) * 2))
+      + _key_pairs                        \
+      * _Configure_From_workspace(sizeof(POSIX_Keys_Rbtree_node)))
   #endif
 
   #ifndef CONFIGURE_MAXIMUM_POSIX_TIMERS
@@ -1835,7 +1842,8 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
       CONFIGURE_MEMORY_FOR_POSIX_CONDITION_VARIABLES( \
           CONFIGURE_MAXIMUM_POSIX_CONDITION_VARIABLES + \
           CONFIGURE_MAXIMUM_GO_CHANNELS + CONFIGURE_GO_INIT_CONDITION_VARIABLES) + \
-      CONFIGURE_MEMORY_FOR_POSIX_KEYS( CONFIGURE_MAXIMUM_POSIX_KEYS ) + \
+      CONFIGURE_MEMORY_FOR_POSIX_KEYS( CONFIGURE_MAXIMUM_POSIX_KEYS, \
+                                       CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS ) + \
       CONFIGURE_MEMORY_FOR_POSIX_QUEUED_SIGNALS( \
           CONFIGURE_MAXIMUM_POSIX_QUEUED_SIGNALS ) + \
       CONFIGURE_MEMORY_FOR_POSIX_MESSAGE_QUEUES( \
@@ -2286,6 +2294,7 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
         CONFIGURE_MAXIMUM_ADA_TASKS + CONFIGURE_MAXIMUM_FAKE_ADA_TASKS +
         CONFIGURE_GO_INIT_CONDITION_VARIABLES + CONFIGURE_MAXIMUM_GO_CHANNELS,
       CONFIGURE_MAXIMUM_POSIX_KEYS,
+      CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS,
       CONFIGURE_MAXIMUM_POSIX_TIMERS,
       CONFIGURE_MAXIMUM_POSIX_QUEUED_SIGNALS,
       CONFIGURE_MAXIMUM_POSIX_MESSAGE_QUEUES,
@@ -2529,7 +2538,8 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
     CONFIGURE_MEMORY_FOR_POSIX_CONDITION_VARIABLES(
       CONFIGURE_MAXIMUM_POSIX_CONDITION_VARIABLES +
       CONFIGURE_MAXIMUM_GO_CHANNELS + CONFIGURE_GO_INIT_CONDITION_VARIABLES),
-    CONFIGURE_MEMORY_FOR_POSIX_KEYS( CONFIGURE_MAXIMUM_POSIX_KEYS ),
+    CONFIGURE_MEMORY_FOR_POSIX_KEYS( CONFIGURE_MAXIMUM_POSIX_KEYS, \
+                                     CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS ),
     CONFIGURE_MEMORY_FOR_POSIX_QUEUED_SIGNALS(
       CONFIGURE_MAXIMUM_POSIX_QUEUED_SIGNALS ),
     CONFIGURE_MEMORY_FOR_POSIX_MESSAGE_QUEUES(
@@ -2600,6 +2610,7 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
        (CONFIGURE_MAXIMUM_POSIX_MUTEXES != 0) || \
        (CONFIGURE_MAXIMUM_POSIX_CONDITION_VARIABLES != 0) || \
        (CONFIGURE_MAXIMUM_POSIX_KEYS != 0) || \
+       (CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS != 0) || \
        (CONFIGURE_MAXIMUM_POSIX_TIMERS != 0) || \
        (CONFIGURE_MAXIMUM_POSIX_QUEUED_SIGNALS != 0) || \
        (CONFIGURE_MAXIMUM_POSIX_MESSAGE_QUEUES != 0) || \
@@ -2671,5 +2682,19 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
   #error "Fewer POSIX Message Queue descriptors than Queues!"
 #endif
 
+/*
+ * POSIX Key pair shouldn't be less than POSIX Key, which is highly
+ * likely to be error.
+ */
+#if defined(RTEMS_POSIX_API)
+    #if (CONFIGURE_MAXIMUM_POSIX_KEYS != 0) && \
+      (CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS != 0)
+      #if (CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS < \
+        CONFIGURE_MAXIMUM_POSIX_KEYS)
+      #error "Fewer POSIX Key pairs than POSIX Key!"
+      #endif
+    #endif
+#endif
+
 #endif
 /* end of include file */
-- 
1.7.1




More information about the devel mailing list