Unlimited objects support for POSIX keys

This patch enables unlimited model in POSIX key manger and have a decent
runtime on POSIX key searching, adding and deleting operations.  Memory
overhead is lower than current implementation when the size of key and key
value becomes big.

11 files changed, 374 insertions, 165 deletions

diff --git a/cpukit/posix/include/rtems/posix/config.h b/cpukit/posix/include/rtems/posix/config.h
index 104bd84046..a842f7a453 100644
--- a/cpukit/posix/include/rtems/posix/config.h
+++ b/cpukit/posix/include/rtems/posix/config.h
@@ -51,6 +51,7 @@ typedef struct {
   uint32_t                            maximum_mutexes;
   uint32_t                            maximum_condition_variables;
   uint32_t                            maximum_keys;
+  uint32_t                            maximum_key_value_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 6d2ebff6fd..ee5b573c9b 100644
--- a/cpukit/posix/include/rtems/posix/key.h
+++ b/cpukit/posix/include/rtems/posix/key.h
@@ -1,6 +1,6 @@
 /**
  * @file
- * 
+ *
  * @brief POSIX Key Private Support
  *
  * This include file contains all the private support information for
@@ -8,24 +8,28 @@
  */
 
 /*
- *  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/rbtree.h>
+#include <rtems/score/chainimpl.h>
+#include <rtems/score/freechain.h>
 #include <rtems/score/objectimpl.h>
 
 /**
  * @defgroup POSIX_KEY POSIX Key
  *
  * @ingroup POSIXAPI
- * 
+ *
  */
 /**@{**/
 
@@ -34,40 +38,86 @@ 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 Key_values_per_thread_node;
+  /** This field is the rbtree node structure. */
+  RBTree_Node Key_value_lookup_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_Key_value_pair;
+
+/**
+ * @brief POSIX_Keys_Freechain is used in Freechain structure
+ */
+typedef struct {
+    Freechain_Control super_fc;
+    size_t bump_count;
+} POSIX_Keys_Freechain;
+
+/**
+ * @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 POSIX keys manager initialization.
+ * @brief The rbtree control block used to manage all key values
+ */
+POSIX_EXTERN RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
+
+/**
+ * @brief This freechain is used as a memory pool for POSIX_Keys_Key_value_pair.
+ */
+POSIX_EXTERN POSIX_Keys_Freechain _POSIX_Keys_Keypool;
+
+/**
+ * @brief POSIX key manager initialization.
  *
  * This routine performs the initialization necessary for this manager.
  */
 void _POSIX_Key_Manager_initialization(void);
 
 /**
+ * @brief POSIX key Freechain extend handle
+ *
+ * This routine extend freechain node, which is called in freechain_get
+ * automatically.
+ */
+bool _POSIX_Keys_Freechain_extend(Freechain_Control *freechain);
+
+/**
+ * @brief POSIX keys Red-Black tree node comparison.
+ *
+ * This routine compares the rbtree node
+ */
+int _POSIX_Keys_Key_value_lookup_tree_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
  * keys.  This function will execute until all values have been set to NULL.
  *
- * @param[in] thread is a pointer to the thread whose keys should have 
+ * @param[in] thread is a pointer to the thread whose keys should have
  *            all their destructors run.
  *
  * NOTE: This is the routine executed when a thread exits to
diff --git a/cpukit/posix/include/rtems/posix/threadsup.h b/cpukit/posix/include/rtems/posix/threadsup.h
index 414b46fd83..7bd1f934ad 100644
--- a/cpukit/posix/include/rtems/posix/threadsup.h
+++ b/cpukit/posix/include/rtems/posix/threadsup.h
@@ -83,6 +83,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 6eace26eed..2bb415c4d5 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,115 @@
 #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>
+#include <rtems/score/freechain.h>
 
-/*
- *  _POSIX_Key_Manager_initialization
- *
- *  DESCRIPTION:
- *
- *  This routine performs the initialization necessary for this manager.
+/* forward declarations to avoid warnings */
+void _POSIX_Keys_Keypool_init(void);
+void _POSIX_Keys_Freechain_init(Freechain_Control *freechain);
+
+/**
+ * @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_Key_value_lookup_tree_compare_function(
+  const RBTree_Node *node1,
+  const RBTree_Node *node2
+)
+{
+  POSIX_Keys_Key_value_pair *n1;
+  POSIX_Keys_Key_value_pair *n2;
+  Objects_Id thread_id1, thread_id2;
+  int diff;
+
+  n1 = _RBTree_Container_of( node1, POSIX_Keys_Key_value_pair, Key_value_lookup_node );
+  n2 = _RBTree_Container_of( node2, POSIX_Keys_Key_value_pair, Key_value_lookup_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 does keypool initialize, keypool contains all
+ * POSIX_Keys_Key_value_pair
+ */
+
+void _POSIX_Keys_Keypool_init(void)
+{
+  _Freechain_Initialize((Freechain_Control *)&_POSIX_Keys_Keypool,
+                       &_POSIX_Keys_Freechain_extend);
+
+  _POSIX_Keys_Freechain_init((Freechain_Control *)&_POSIX_Keys_Keypool);
+}
+
+/**
+ * @brief This routine does user side freechain initialization
+ */
+void _POSIX_Keys_Freechain_init(Freechain_Control *freechain)
+{
+  POSIX_Keys_Freechain *psx_freechain_p = (POSIX_Keys_Freechain *)freechain;
+  psx_freechain_p->bump_count =
+    Configuration_POSIX_API.maximum_key_value_pairs & 0x7FFFFFFF;
+  size_t size = psx_freechain_p->bump_count * sizeof(POSIX_Keys_Key_value_pair);
+  POSIX_Keys_Key_value_pair *nodes = _Workspace_Allocate(size);
+
+  _Chain_Initialize(
+                    &freechain->Freechain,
+                    nodes,
+                    psx_freechain_p->bump_count,
+                    sizeof(POSIX_Keys_Key_value_pair)
+                    );
+}
+
+/**
+ * @brief This routine is user defined freechain extension handle
+ */
+bool _POSIX_Keys_Freechain_extend(Freechain_Control *freechain)
+{
+  POSIX_Keys_Freechain *psx_freechain_p = (POSIX_Keys_Freechain *)freechain;
+  size_t node_size = sizeof(POSIX_Keys_Key_value_pair);
+  size_t size = psx_freechain_p->bump_count * node_size;
+  int i;
+  POSIX_Keys_Key_value_pair *nodes = _Workspace_Allocate(size);
+
+  if (!nodes)
+    return false;
+
+  for ( i = 0; i < psx_freechain_p->bump_count; i++ ) {
+      _Freechain_Put(freechain,
+                     nodes + i);
+  }
+  return true;
+}
+
+/**
+ * @brief This routine performs the initialization necessary for this manager.
+ */
 void _POSIX_Key_Manager_initialization(void)
 {
   _Objects_Initialize_information(
@@ -60,4 +157,12 @@ void _POSIX_Key_Manager_initialization(void)
     NULL                        /* Proxy extraction support callout */
 #endif
   );
+
+  _RBTree_Initialize_empty(
+      &_POSIX_Keys_Key_value_lookup_tree,
+      _POSIX_Keys_Key_value_lookup_tree_compare_function,
+      true
+  );
+
+  _POSIX_Keys_Keypool_init();
 }
diff --git a/cpukit/posix/src/keycreate.c b/cpukit/posix/src/keycreate.c
index b41b59017e..349e88378a 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
@@ -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,50 +48,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 8f96ca36fe..c3d3da1a3b 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,7 +49,7 @@ int pthread_key_delete(
        *         of the application to free the memory.
        */
       _POSIX_Keys_Free( the_key );
-      _Objects_Put( &the_key->Object );
+      _Objects_Put(&the_key->Object);
       return 0;
 
 #if defined(RTEMS_MULTIPROCESSING)
diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
index f71af4f327..c42616dcb0 100644
--- a/cpukit/posix/src/keyfreememory.c
+++ b/cpukit/posix/src/keyfreememory.c
@@ -1,17 +1,18 @@
 /**
  * @file
  *
- * @brief POSIX Function Keys Free Memory 
+ * @brief POSIX Function Keys Free Memory
  * @ingroup POSIXAPI
  */
 
 /*
- *  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,45 @@
 #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_Key_value_pair search_node;
+  POSIX_Keys_Key_value_pair *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_Key_value_lookup_tree, &search_node.Key_value_lookup_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_Key_value_pair, Key_value_lookup_node );
+  while ( p->key == the_key->Object.id) {
+    iter = next;
+    next = _RBTree_Next_unprotected( iter, RBT_LEFT );
+    p = _RBTree_Container_of( next, POSIX_Keys_Key_value_pair, Key_value_lookup_node );
+  }
+
+  /**
+   * delete all nodes belongs to the_key from the rbtree and chain.
+   */
+  p = _RBTree_Container_of( iter, POSIX_Keys_Key_value_pair, Key_value_lookup_node );
+  while ( p->key == the_key->Object.id ) {
+    next = _RBTree_Next_unprotected( iter, RBT_RIGHT );
+    _RBTree_Extract_unprotected( &_POSIX_Keys_Key_value_lookup_tree, iter );
+    _Chain_Extract_unprotected( &p->Key_values_per_thread_node );
+    /* append the node to _POSIX_Keys_Keypool */
+    _Freechain_Put( &_POSIX_Keys_Keypool.super_fc,
+                    ( void * )p);
+    iter = next;
+    p = _RBTree_Container_of( iter, POSIX_Keys_Key_value_pair, Key_value_lookup_node );
+  }
 }
diff --git a/cpukit/posix/src/keygetspecific.c b/cpukit/posix/src/keygetspecific.c
index 0e8bbcdec8..88e084ee96 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,20 +38,31 @@ void *pthread_getspecific(
   pthread_key_t  key
 )
 {
-  register POSIX_Keys_Control *the_key;
-  uint32_t                     api;
-  uint32_t                     index;
   Objects_Locations            location;
+  POSIX_Keys_Key_value_pair    search_node;
+  RBTree_Node                 *p;
   void                        *key_data;
+  POSIX_Keys_Key_value_pair   *value_pair_p;
 
-  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 ];
-      _Objects_Put( &the_key->Object );
+      search_node.key = key;
+      search_node.thread_id = _Thread_Executing->Object.id;
+      p = _RBTree_Find_unprotected( &_POSIX_Keys_Key_value_lookup_tree,
+                                    &search_node.Key_value_lookup_node );
+      key_data = NULL;
+      if ( p ) {
+        value_pair_p = _RBTree_Container_of( p,
+                                          POSIX_Keys_Key_value_pair,
+                                          Key_value_lookup_node );
+        /* key_data = _RBTree_Container_of( p, */
+        /*                                  POSIX_Keys_Key_value_pair, */
+        /*                                  Key_value_lookup_node )->value; */
+        key_data = value_pair_p->value;
+      }
+      _Thread_Enable_dispatch();
       return key_data;
 
 #if defined(RTEMS_MULTIPROCESSING)
diff --git a/cpukit/posix/src/keyrundestructors.c b/cpukit/posix/src/keyrundestructors.c
index eb692e0dc9..7e3c88fdb6 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
@@ -22,7 +23,10 @@
 
 #include <rtems/system.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
@@ -32,41 +36,60 @@
  *  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;
+  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_Key_value_pair *,
+     * because Chain_Node is the first member of POSIX_Keys_Key_value_pair
+     * structure.
+     */
+    _RBTree_Extract_unprotected(
+        &_POSIX_Keys_Key_value_lookup_tree,
+        &((POSIX_Keys_Key_value_pair *)iter)->Key_value_lookup_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_Key_value_pair *)iter)->key,
+        &location
+    );
+    destructor = the_key->destructor;
+    value = ((POSIX_Keys_Key_value_pair *)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 ];
+    /**
+     * put back this node to keypool
+     */
+    _Freechain_Put( &_POSIX_Keys_Keypool.super_fc,
+                    (void *)iter );
 
-        if ( value != NULL ) {
-          key->Values [ thread_api ][ thread_index ] = NULL;
-          (*key->destructor)( value );
-          done = false;
-        }
-      }
-    }
+    iter = next;
   }
+  _Thread_Enable_dispatch();
 }
diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
index 22eb8eb643..f527fe1ee4 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,19 +41,38 @@ int pthread_setspecific(
   const void    *value
 )
 {
-  register POSIX_Keys_Control *the_key;
-  uint32_t                     api;
-  uint32_t                     index;
   Objects_Locations            location;
+  POSIX_Keys_Key_value_pair   *value_pair_ptr;
+  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;
-      _Objects_Put( &the_key->Object );
+      value_pair_ptr = ( POSIX_Keys_Key_value_pair * )
+        _Freechain_Get( &_POSIX_Keys_Keypool.super_fc );
+      if ( !value_pair_ptr ) {
+        _Thread_Enable_dispatch();
+        return ENOMEM;
+      }
+
+      value_pair_ptr->key = key;
+      value_pair_ptr->thread_id = _Thread_Executing->Object.id;
+      value_pair_ptr->value = value;
+      if ( _RBTree_Insert_unprotected( &_POSIX_Keys_Key_value_lookup_tree,
+                                       &(value_pair_ptr->Key_value_lookup_node) ) ) {
+        _Freechain_Put( (Freechain_Control *)&_POSIX_Keys_Keypool,
+                        (void *) value_pair_ptr );
+        _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, &value_pair_ptr->Key_values_per_thread_node );
+
+      _Thread_Enable_dispatch();
       return 0;
 
 #if defined(RTEMS_MULTIPROCESSING)
diff --git a/cpukit/posix/src/pthread.c b/cpukit/posix/src/pthread.c
index 121b0874e7..13f7525c75 100644
--- a/cpukit/posix/src/pthread.c
+++ b/cpukit/posix/src/pthread.c
@@ -236,6 +236,9 @@ static bool _POSIX_Threads_Create_extension(
     created
   );
 
+  /** initialize thread's key vaule node chain */
+  _Chain_Initialize_empty( &api->Key_Chain );
+
   return true;
 }