posix: Use per-thread lookup tree for POSIX Keys

Yields higher performance on SMP systems.

Close #2625.

13 files changed, 326 insertions, 409 deletions

diff --git a/cpukit/libcsupport/src/resource_snapshot.c b/cpukit/libcsupport/src/resource_snapshot.c
index d6f2e4606e..198015593f 100644
--- a/cpukit/libcsupport/src/resource_snapshot.c
+++ b/cpukit/libcsupport/src/resource_snapshot.c
@@ -105,31 +105,24 @@ static void get_heap_info(Heap_Control *heap, Heap_Information_block *info)
   memset(&info->Stats, 0, sizeof(info->Stats));
 }
 
-static bool count_posix_key_value_pairs(
-  const RBTree_Node *node,
-  void *visitor_arg
-)
+static POSIX_Keys_Control *get_next_key(Objects_Id *id)
 {
-  uint32_t *count = visitor_arg;
-
-  (void) node;
+  Objects_Locations location;
 
-  ++(*count);
-
-  return false;
+  return (POSIX_Keys_Control *)
+    _Objects_Get_next(&_POSIX_Keys_Information, *id, &location, id);
 }
 
 static uint32_t get_active_posix_key_value_pairs(void)
 {
   uint32_t count = 0;
+  Objects_Id id = OBJECTS_ID_INITIAL_INDEX;
+  POSIX_Keys_Control *the_key;
 
-  _Thread_Disable_dispatch();
-  _RBTree_Iterate(
-    &_POSIX_Keys_Key_value_lookup_tree,
-    count_posix_key_value_pairs,
-    &count
-  );
-  _Thread_Enable_dispatch();
+  while ((the_key = get_next_key(&id)) != NULL ) {
+    count += _Chain_Node_count_unprotected(&the_key->Key_value_pairs);
+    _Objects_Allocator_unlock();
+  }
 
   return count;
 }
diff --git a/cpukit/posix/Makefile.am b/cpukit/posix/Makefile.am
index 62a2a5aa3f..dcedf5b77d 100644
--- a/cpukit/posix/Makefile.am
+++ b/cpukit/posix/Makefile.am
@@ -154,7 +154,7 @@ endif
 
 ## KEY_C_FILES
 libposix_a_SOURCES += src/key.c src/keycreate.c src/keydelete.c \
-    src/keygetspecific.c src/keyfreememory.c \
+    src/keygetspecific.c \
     src/keysetspecific.c
 
 ## ONCE_C_FILES
diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
index 6e52544686..1f09916f06 100644
--- a/cpukit/posix/include/rtems/posix/key.h
+++ b/cpukit/posix/include/rtems/posix/key.h
@@ -11,6 +11,7 @@
  * Copyright (c) 2012 Zhongwei Yao.
  * COPYRIGHT (c) 1989-2011.
  * On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.
  *
  * The license and distribution terms for this file may be
  * found in the file LICENSE in this distribution or at
@@ -44,24 +45,22 @@ extern "C" {
  */
 typedef struct {
   /**
-   * @brief The chain node for the per-thread value chain.
+   * @brief The chain node for the key value pairs chain in POSIX_Keys_Control.
    */
-  Chain_Node Key_values_per_thread_node;
+  Chain_Node Key_node;
 
   /**
-   * @brief The tree node for the lookup tree.
+   * @brief The tree node for the lookup tree in Thread_Keys_information.
    */
-  RBTree_Node Key_value_lookup_node;
+  RBTree_Node Lookup_node;
 
   /**
-   * @brief The POSIX key identifier used in combination with the thread
-   * pointer as the tree key.
+   * @brief The POSIX key identifier used as the tree key.
    */
   pthread_key_t key;
 
   /**
-   * @brief The thread pointer used in combination with the POSIX key
-   * identifier as the tree key.
+   * @brief The corresponding thread.
    */
   Thread_Control *thread;
 
@@ -79,6 +78,11 @@ typedef struct {
    Objects_Control     Object;
    /** This field is the data destructor. */
    void (*destructor) (void *);
+
+   /**
+    * @brief Key value pairs of this key.
+    */
+   Chain_Control Key_value_pairs;
  }  POSIX_Keys_Control;
 
 /** @} */
diff --git a/cpukit/posix/include/rtems/posix/keyimpl.h b/cpukit/posix/include/rtems/posix/keyimpl.h
index 1addb1e376..28666aa925 100644
--- a/cpukit/posix/include/rtems/posix/keyimpl.h
+++ b/cpukit/posix/include/rtems/posix/keyimpl.h
@@ -10,6 +10,7 @@
 /*
  *  COPYRIGHT (c) 1989-1999.
  *  On-Line Applications Research Corporation (OAR).
+ *  Copyright (c) 2016 embedded brains GmbH.
  *
  *  The license and distribution terms for this file may be
  *  found in the file LICENSE in this distribution or at
@@ -41,51 +42,12 @@ extern "C" {
 extern Objects_Information _POSIX_Keys_Information;
 
 /**
- * @brief The rbtree control block used to manage all key values
- */
-extern RBTree_Control _POSIX_Keys_Key_value_lookup_tree;
-
-/**
  * @brief This freechain is used as a memory pool for POSIX_Keys_Key_value_pair.
  */
 extern Freechain_Control _POSIX_Keys_Keypool;
 
 #define POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node ) \
-  RTEMS_CONTAINER_OF( node, POSIX_Keys_Key_value_pair, Key_value_lookup_node )
-
-/**
- * @brief POSIX keys Red-Black tree node comparison.
- *
- * This routine compares the rbtree node
- */
-RBTree_Compare_result _POSIX_Keys_Key_value_compare(
-  const RBTree_Node *node1,
-  const RBTree_Node *node2
-);
-
-/**
- * @brief Free a POSIX key table memory.
- *
- * This memory frees the key table memory associated with @a the_key.
- *
- * @param[in] the_key is a pointer to the POSIX key to free
- * the table memory of.
- */
-void _POSIX_Keys_Free_memory(
-  POSIX_Keys_Control *the_key
-);
-
-/**
- * @brief Free a POSIX keys control block.
- *
- * This routine frees a keys control block to the
- * inactive chain of free keys control blocks.
- *
- * @param[in] the_key is a pointer to the POSIX key to free.
- */
-RTEMS_INLINE_ROUTINE void _POSIX_Keys_Free (
-  POSIX_Keys_Control *the_key
-);
+  RTEMS_CONTAINER_OF( node, POSIX_Keys_Key_value_pair, Lookup_node )
 
 /**
  * @brief Allocate a keys control block.
@@ -105,71 +67,111 @@ RTEMS_INLINE_ROUTINE POSIX_Keys_Control *_POSIX_Keys_Allocate( void )
  * This routine frees a keys control block to the
  * inactive chain of free keys control blocks.
  */
-RTEMS_INLINE_ROUTINE void _POSIX_Keys_Free (
+RTEMS_INLINE_ROUTINE void _POSIX_Keys_Free(
   POSIX_Keys_Control *the_key
 )
 {
   _Objects_Free( &_POSIX_Keys_Information, &the_key->Object );
 }
 
-/**
- * @brief Get a keys control block.
- *
- * This function maps key IDs to key control blocks.
- * If ID corresponds to a local keys, then it returns
- * the_key control pointer which maps to ID and location
- * is set to OBJECTS_LOCAL.  if the keys ID is global and
- * resides on a remote node, then location is set to OBJECTS_REMOTE,
- * and the_key is undefined.  Otherwise, location is set
- * to OBJECTS_ERROR and the_key is undefined.
- */
+RTEMS_INLINE_ROUTINE POSIX_Keys_Control *_POSIX_Keys_Get( pthread_key_t key )
+{
+  Objects_Locations location;
+
+  return (POSIX_Keys_Control *) _Objects_Get_no_protection(
+    &_POSIX_Keys_Information,
+    (Objects_Id) key,
+    &location
+  );
+}
+
+RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_acquire(
+  Thread_Control   *the_thread,
+  ISR_lock_Context *lock_context
+)
+{
+  _ISR_lock_ISR_disable_and_acquire( &the_thread->Keys.Lock, lock_context );
+}
 
-RTEMS_INLINE_ROUTINE POSIX_Keys_Control *_POSIX_Keys_Get (
-  pthread_key_t      id,
-  Objects_Locations *location
+RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_release(
+  Thread_Control   *the_thread,
+  ISR_lock_Context *lock_context
 )
 {
-  return (POSIX_Keys_Control *)
-    _Objects_Get( &_POSIX_Keys_Information, (Objects_Id) id, location );
+  _ISR_lock_Release_and_ISR_enable( &the_thread->Keys.Lock, lock_context );
 }
 
-POSIX_Keys_Key_value_pair * _POSIX_Keys_Key_value_pair_allocate( void );
+POSIX_Keys_Key_value_pair * _POSIX_Keys_Key_value_allocate( void );
 
-RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_pair_free(
+RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_free(
   POSIX_Keys_Key_value_pair *key_value_pair
 )
 {
+  _Chain_Extract_unprotected( &key_value_pair->Key_node );
   _Freechain_Put( &_POSIX_Keys_Keypool, key_value_pair );
 }
 
-RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Find(
-  pthread_key_t   key,
-  Thread_Control *thread
+RTEMS_INLINE_ROUTINE RBTree_Node *_POSIX_Keys_Key_value_find(
+  pthread_key_t     key,
+  Thread_Control   *the_thread
 )
 {
-  POSIX_Keys_Key_value_pair search_node;
-
-  search_node.key = key;
-  search_node.thread = thread;
-
-  return _RBTree_Find(
-    &_POSIX_Keys_Key_value_lookup_tree,
-    &search_node.Key_value_lookup_node,
-    _POSIX_Keys_Key_value_compare,
-    true
-  );
+  RBTree_Node **link;
+  RBTree_Node  *parent;
+
+  link = _RBTree_Root_reference( &the_thread->Keys.Key_value_pairs );
+  parent = NULL;
+
+  while ( *link != NULL ) {
+    POSIX_Keys_Key_value_pair *parent_key_value_pair;
+    pthread_key_t              parent_key;
+
+    parent = *link;
+    parent_key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( parent );
+    parent_key = parent_key_value_pair->key;
+
+    if ( key == parent_key ) {
+      return parent;
+    } else if ( key < parent_key ) {
+      link = _RBTree_Left_reference( parent );
+    } else {
+      link = _RBTree_Right_reference( parent );
+    }
+  }
+
+  return NULL;
 }
 
-RTEMS_INLINE_ROUTINE void _POSIX_Keys_Free_key_value_pair(
-  POSIX_Keys_Key_value_pair *key_value_pair
+RTEMS_INLINE_ROUTINE void _POSIX_Keys_Key_value_insert(
+  pthread_key_t              key,
+  POSIX_Keys_Key_value_pair *key_value_pair,
+  Thread_Control            *the_thread
 )
 {
-  _RBTree_Extract(
-    &_POSIX_Keys_Key_value_lookup_tree,
-    &key_value_pair->Key_value_lookup_node
+  RBTree_Node **link;
+  RBTree_Node  *parent;
+
+  link = _RBTree_Root_reference( &the_thread->Keys.Key_value_pairs );
+  parent = NULL;
+
+  while ( *link != NULL ) {
+    POSIX_Keys_Key_value_pair *parent_key_value_pair;
+
+    parent = *link;
+    parent_key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( parent );
+
+    if ( key < parent_key_value_pair->key ) {
+      link = _RBTree_Left_reference( parent );
+    } else {
+      link = _RBTree_Right_reference( parent );
+    }
+  }
+
+  _RBTree_Add_child( &key_value_pair->Lookup_node, parent, link );
+  _RBTree_Insert_color(
+    &the_thread->Keys.Key_value_pairs,
+    &key_value_pair->Lookup_node
   );
-  _Chain_Extract_unprotected( &key_value_pair->Key_values_per_thread_node );
-  _POSIX_Keys_Key_value_pair_free( key_value_pair );
 }
 
 /** @} */
diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
index 5a0886b980..389a28b878 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -9,6 +9,7 @@
  * Copyright (c) 2012 Zhongwei Yao.
  * COPYRIGHT (c) 1989-2014.
  * On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.
  *
  * The license and distribution terms for this file may be
  * found in the file LICENSE in this distribution or at
@@ -23,66 +24,13 @@
 #include <rtems/sysinit.h>
 
 #include <rtems/posix/keyimpl.h>
-#include <rtems/score/chainimpl.h>
-#include <rtems/score/objectimpl.h>
 #include <rtems/score/userextimpl.h>
 #include <rtems/score/wkspace.h>
 
 Objects_Information _POSIX_Keys_Information;
 
-RBTREE_DEFINE_EMPTY( _POSIX_Keys_Key_value_lookup_tree );
-
 Freechain_Control _POSIX_Keys_Keypool;
 
-/**
- * @brief This routine compares the rbtree node by comparing POSIX key first
- * and comparing thread id second.
- *
- * 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.
- *
- * @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
- */
-
-RBTree_Compare_result _POSIX_Keys_Key_value_compare(
-  const RBTree_Node *node1,
-  const RBTree_Node *node2
-)
-{
-  POSIX_Keys_Key_value_pair *n1;
-  POSIX_Keys_Key_value_pair *n2;
-  Thread_Control *thread1;
-  Thread_Control *thread2;
-  RBTree_Compare_result diff;
-
-  n1 = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node1 );
-  n2 = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node2 );
-
-  diff = n1->key - n2->key;
-  if ( diff )
-    return diff;
-
-  thread1 = n1->thread;
-  thread2 = n2->thread;
-
-  /*
-   * If thread1 or thread2 equals to NULL, only key1 and key2 is valued.  It
-   * enables us search node only by pthread_key_t type key.  Exploit that the
-   * thread control alignment is at least two to avoid integer overflows.
-   */
-  if ( thread1 != NULL && thread2 != NULL )
-    return (RBTree_Compare_result) ( (uintptr_t) thread1 >> 1 )
-      - (RBTree_Compare_result) ( (uintptr_t) thread2 >> 1 );
-
-  return 0;
-}
-
 static uint32_t _POSIX_Keys_Get_keypool_bump_count( void )
 {
   uint32_t max = Configuration.maximum_key_value_pairs;
@@ -108,7 +56,7 @@ static void _POSIX_Keys_Initialize_keypool( void )
   );
 }
 
-POSIX_Keys_Key_value_pair * _POSIX_Keys_Key_value_pair_allocate( void )
+POSIX_Keys_Key_value_pair * _POSIX_Keys_Key_value_allocate( void )
 {
   return (POSIX_Keys_Key_value_pair *) _Freechain_Get(
     &_POSIX_Keys_Keypool,
@@ -118,50 +66,48 @@ POSIX_Keys_Key_value_pair * _POSIX_Keys_Key_value_pair_allocate( void )
   );
 }
 
-static void _POSIX_Keys_Run_destructors( Thread_Control *thread )
+static void _POSIX_Keys_Run_destructors( Thread_Control *the_thread )
 {
-  Chain_Control *chain;
-  POSIX_Keys_Key_value_pair *iter, *next;
-  void *value;
-  void (*destructor) (void *);
-  POSIX_Keys_Control *the_key;
-  Objects_Locations location;
-
-  chain = &thread->Key_Chain;
-  iter = (POSIX_Keys_Key_value_pair *) _Chain_First( chain );
-  while ( !_Chain_Is_tail( chain, &iter->Key_values_per_thread_node ) ) {
-    next = (POSIX_Keys_Key_value_pair *)
-      _Chain_Next( &iter->Key_values_per_thread_node );
-
-    the_key = _POSIX_Keys_Get( iter->key, &location );
-    _Assert( location == OBJECTS_LOCAL );
-
-    /**
-     * 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(
-        &_POSIX_Keys_Key_value_lookup_tree,
-        &iter->Key_value_lookup_node
-    );
-    _Chain_Extract_unprotected( &iter->Key_values_per_thread_node );
-
-    destructor = the_key->destructor;
-    value = iter->value;
-
-    _POSIX_Keys_Key_value_pair_free( iter );
-
-    _Objects_Put( &the_key->Object );
-
-    /**
-     * run key value's destructor if destructor and value are both non-null.
-     */
-    if ( destructor != NULL && value != NULL )
-      (*destructor)( value );
-
-    iter = next;
+  while ( true ) {
+    ISR_lock_Context  lock_context;
+    RBTree_Node      *node;
+
+    _Objects_Allocator_lock();
+    _POSIX_Keys_Key_value_acquire( the_thread, &lock_context );
+
+    node = _RBTree_Root( &the_thread->Keys.Key_value_pairs );
+    if ( node != NULL ) {
+      POSIX_Keys_Key_value_pair *key_value_pair;
+      pthread_key_t              key;
+      void                      *value;
+      POSIX_Keys_Control        *the_key;
+      void                    ( *destructor )( void * );
+
+      key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node );
+      key = key_value_pair->key;
+      value = key_value_pair->value;
+      _RBTree_Extract(
+        &the_thread->Keys.Key_value_pairs,
+        &key_value_pair->Lookup_node
+      );
+
+      _POSIX_Keys_Key_value_release( the_thread, &lock_context );
+      _POSIX_Keys_Key_value_free( key_value_pair );
+
+      the_key = _POSIX_Keys_Get( key );
+      _Assert( the_key != NULL );
+      destructor = the_key->destructor;
+
+      _Objects_Allocator_unlock();
+
+      if ( destructor != NULL && value != NULL ) {
+        ( *destructor )( value );
+      }
+    } else {
+      _POSIX_Keys_Key_value_release( the_thread, &lock_context );
+      _Objects_Allocator_unlock();
+      break;
+    }
   }
 }
 
diff --git a/cpukit/posix/src/keycreate.c b/cpukit/posix/src/keycreate.c
index 245ac9e3f3..432bfd86b6 100644
--- a/cpukit/posix/src/keycreate.c
+++ b/cpukit/posix/src/keycreate.c
@@ -8,6 +8,7 @@
 /*
  * COPYRIGHT (c) 1989-2010.
  * On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.
  *
  * The license and distribution terms for this file may be
  * found in the file LICENSE in this distribution or at
@@ -18,16 +19,10 @@
 #include "config.h"
 #endif
 
-#include <errno.h>
-#include <limits.h>
-#include <pthread.h>
-#include <string.h>
-
-#include <rtems/system.h>
-#include <rtems/score/thread.h>
-#include <rtems/score/wkspace.h>
 #include <rtems/posix/keyimpl.h>
 
+#include <errno.h>
+
 /**
  *  17.1.1 Thread-Specific Data Key Create, P1003.1c/Draft 10, p. 163
  */
@@ -46,6 +41,7 @@ int pthread_key_create(
   }
 
   the_key->destructor = destructor;
+  _Chain_Initialize_empty( &the_key->Key_value_pairs );
   _Objects_Open_u32( &_POSIX_Keys_Information, &the_key->Object, 0 );
   *key = the_key->Object.id;
   _Objects_Allocator_unlock();
diff --git a/cpukit/posix/src/keydelete.c b/cpukit/posix/src/keydelete.c
index 392558f0f8..a3abca7c04 100644
--- a/cpukit/posix/src/keydelete.c
+++ b/cpukit/posix/src/keydelete.c
@@ -8,6 +8,7 @@
 /*
  * COPYRIGHT (c) 1989-2007.
  * On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.
  *
  * The license and distribution terms for this file may be
  * found in the file LICENSE in this distribution or at
@@ -18,15 +19,38 @@
 #include "config.h"
 #endif
 
+#include <rtems/posix/keyimpl.h>
+
 #include <errno.h>
-#include <limits.h>
-#include <pthread.h>
-#include <string.h>
 
-#include <rtems/system.h>
-#include <rtems/score/thread.h>
-#include <rtems/score/wkspace.h>
-#include <rtems/posix/keyimpl.h>
+static void _POSIX_Keys_Destroy( POSIX_Keys_Control *the_key )
+{
+  _Objects_Close( &_POSIX_Keys_Information, &the_key->Object );
+
+  while ( true ) {
+    POSIX_Keys_Key_value_pair *key_value_pair;
+    ISR_lock_Context           lock_context;
+    Thread_Control            *the_thread;
+
+    key_value_pair = (POSIX_Keys_Key_value_pair *)
+      _Chain_Get_unprotected( &the_key->Key_value_pairs );
+    if ( key_value_pair == NULL ) {
+      break;
+    }
+
+    the_thread = key_value_pair->thread;
+    _POSIX_Keys_Key_value_acquire( the_thread, &lock_context );
+    _RBTree_Extract(
+      &the_thread->Keys.Key_value_pairs,
+      &key_value_pair->Lookup_node
+    );
+    _POSIX_Keys_Key_value_release( the_thread, &lock_context );
+
+    _POSIX_Keys_Key_value_free( key_value_pair );
+  }
+
+  _Objects_Free( &_POSIX_Keys_Information, &the_key->Object );
+}
 
 /*
  *  17.1.3 Thread-Specific Data Key Deletion, P1003.1c/Draft 10, p. 167
@@ -36,32 +60,19 @@ int pthread_key_delete(
 )
 {
   POSIX_Keys_Control *the_key;
-  Objects_Locations   location;
+  int                 eno;
 
   _Objects_Allocator_lock();
-  the_key = _POSIX_Keys_Get( key, &location );
-  switch ( location ) {
 
-    case OBJECTS_LOCAL:
-      _POSIX_Keys_Free_memory( the_key );
-
-      /*
-       *  NOTE:  The destructor is not called and it is the responsibility
-       *         of the application to free the memory.
-       */
-      _POSIX_Keys_Free( the_key );
-      _Objects_Put(&the_key->Object);
-      _Objects_Allocator_unlock();
-      return 0;
-
-#if defined(RTEMS_MULTIPROCESSING)
-    case OBJECTS_REMOTE:   /* should never happen */
-#endif
-    case OBJECTS_ERROR:
-      break;
+  the_key = _POSIX_Keys_Get( key );
+  if ( the_key != NULL ) {
+    _POSIX_Keys_Destroy( the_key );
+    eno = 0;
+  } else {
+    eno = EINVAL;
   }
 
   _Objects_Allocator_unlock();
 
-  return EINVAL;
+  return eno;
 }
diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
deleted file mode 100644
index 0e2c517cc5..0000000000
--- a/cpukit/posix/src/keyfreememory.c
+++ /dev/null
@@ -1,60 +0,0 @@
-/**
- * @file
- *
- * @brief POSIX Function Keys Free Memory
- * @ingroup POSIXAPI
- */
-
-/*
- * 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.org/license/LICENSE.
- */
-
-#if HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#include <rtems/posix/keyimpl.h>
-#include <rtems/score/chainimpl.h>
-
-void _POSIX_Keys_Free_memory(
-  POSIX_Keys_Control *the_key
-)
-{
-  POSIX_Keys_Key_value_pair *p;
-  RBTree_Node *iter, *next;
-  Objects_Id key_id;
-
-  key_id = the_key->Object.id;
-  iter = _POSIX_Keys_Find( key_id, 0 );
-  if ( !iter )
-    return;
-  /**
-   * find the smallest thread_id node in the rbtree.
-   */
-  next = _RBTree_Predecessor( iter );
-  p = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( next );
-  while ( next != NULL && p->key == key_id) {
-    iter = next;
-    next = _RBTree_Predecessor( iter );
-    p = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( next );
-  }
-
-  /**
-   * delete all nodes belongs to the_key from the rbtree and chain.
-   */
-  p = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( iter );
-  while ( iter != NULL && p->key == key_id ) {
-    next = _RBTree_Successor( iter );
-
-    _POSIX_Keys_Free_key_value_pair( p );
-
-    iter = next;
-    p = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( iter );
-  }
-}
diff --git a/cpukit/posix/src/keygetspecific.c b/cpukit/posix/src/keygetspecific.c
index ef6c19d56c..08ac1ed28c 100644
--- a/cpukit/posix/src/keygetspecific.c
+++ b/cpukit/posix/src/keygetspecific.c
@@ -9,6 +9,7 @@
  * Copyright (c) 2012 Zhongwei Yao.
  * COPYRIGHT (c) 1989-2007.
  * On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.
  *
  * The license and distribution terms for this file may be
  * found in the file LICENSE in this distribution or at
@@ -19,15 +20,6 @@
 #include "config.h"
 #endif
 
-#include <errno.h>
-#include <limits.h>
-#include <pthread.h>
-#include <string.h>
-
-#include <rtems/system.h>
-#include <rtems/score/thread.h>
-#include <rtems/score/wkspace.h>
-#include <rtems/score/rbtree.h>
 #include <rtems/posix/keyimpl.h>
 
 /*
@@ -38,34 +30,26 @@ void *pthread_getspecific(
   pthread_key_t  key
 )
 {
-  POSIX_Keys_Control          *the_key;
-  Objects_Locations            location;
-  RBTree_Node                 *p;
-  void                        *key_data;
-  POSIX_Keys_Key_value_pair   *value_pair_p;
-
-  the_key = _POSIX_Keys_Get( key, &location );
-  switch ( location ) {
+  Thread_Control   *executing;
+  ISR_lock_Context  lock_context;
+  RBTree_Node      *node;
+  void             *value;
 
-    case OBJECTS_LOCAL:
-      p = _POSIX_Keys_Find( key, _Thread_Executing );
-      if ( p != NULL ) {
-        value_pair_p = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( p );
-        key_data = value_pair_p->value;
-      } else {
-        key_data = NULL;
-      }
+  executing = _Thread_Get_executing();
+  _POSIX_Keys_Key_value_acquire( executing, &lock_context );
 
-      _Objects_Put( &the_key->Object );
+  node = _POSIX_Keys_Key_value_find( key, executing );
 
-      return key_data;
+  if ( node != NULL ) {
+    POSIX_Keys_Key_value_pair *key_value_pair;
 
-#if defined(RTEMS_MULTIPROCESSING)
-    case OBJECTS_REMOTE:   /* should never happen */
-#endif
-    case OBJECTS_ERROR:
-      break;
+    key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node );
+    value = key_value_pair->value;
+  } else {
+    value = NULL;
   }
 
-  return NULL;
+  _POSIX_Keys_Key_value_release( executing, &lock_context );
+
+  return value;
 }
diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
index 20e3042b4d..8b0f517eaf 100644
--- a/cpukit/posix/src/keysetspecific.c
+++ b/cpukit/posix/src/keysetspecific.c
@@ -9,6 +9,7 @@
  * Copyright (c) 2012 Zhongwei Yao.
  * COPYRIGHT (c) 1989-2014.
  * On-Line Applications Research Corporation (OAR).
+ * Copyright (c) 2016 embedded brains GmbH.
  *
  * The license and distribution terms for this file may be
  * found in the file LICENSE in this distribution or at
@@ -20,70 +21,106 @@
 #endif
 
 #include <rtems/posix/keyimpl.h>
-#include <rtems/score/thread.h>
-#include <rtems/score/chainimpl.h>
 
 #include <errno.h>
 
-static int _POSIX_Keys_Set_value(
+static int _POSIX_Keys_Set_value( RBTree_Node *node, const void *value )
+{
+  POSIX_Keys_Key_value_pair *key_value_pair;
+
+  key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node );
+  key_value_pair->value = RTEMS_DECONST( void *, value );
+
+  return 0;
+}
+
+static int _POSIX_Keys_Create_value(
   pthread_key_t       key,
   const void         *value,
-  POSIX_Keys_Control *the_key,
-  Thread_Control     *executing,
-  RBTree_Node        *rb_node
+  Thread_Control     *executing
 )
 {
-  POSIX_Keys_Key_value_pair *key_value_pair;
+  POSIX_Keys_Control *the_key;
+  int                 eno;
 
-  if ( rb_node != NULL ) {
-    key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( rb_node );
-    key_value_pair->value = RTEMS_DECONST( void *, value );
-  } else {
-    key_value_pair = _POSIX_Keys_Key_value_pair_allocate();
+  _Objects_Allocator_lock();
+
+  the_key = _POSIX_Keys_Get( key );
+  if ( the_key != NULL ) {
+    POSIX_Keys_Key_value_pair *key_value_pair;
+
+    key_value_pair = _POSIX_Keys_Key_value_allocate();
+    if ( key_value_pair != NULL ) {
+      ISR_lock_Context lock_context;
+
+      key_value_pair->key = key;
+      key_value_pair->thread = executing;
+      key_value_pair->value = RTEMS_DECONST( void *, value );
+
+      _Chain_Append_unprotected(
+        &the_key->Key_value_pairs,
+        &key_value_pair->Key_node
+      );
 
-    if ( key_value_pair == NULL ) {
-      return ENOMEM;
+      _POSIX_Keys_Key_value_acquire( executing, &lock_context );
+      _POSIX_Keys_Key_value_insert( key, key_value_pair, executing );
+      _POSIX_Keys_Key_value_release( executing, &lock_context );
+      eno = 0;
+    } else {
+      eno = ENOMEM;
     }
 
-    key_value_pair->key = key;
-    key_value_pair->thread = executing;
-    key_value_pair->value = RTEMS_DECONST( void *, value );
-
-    /*
-     * The insert can only go wrong if the same node is already in a unique
-     * tree.  This has been already checked with the _RBTree_Find().
-     */
-    _RBTree_Insert(
-      &_POSIX_Keys_Key_value_lookup_tree,
-      &key_value_pair->Key_value_lookup_node,
-      _POSIX_Keys_Key_value_compare,
-      true
-    );
-
-    _Chain_Append_unprotected(
-      &executing->Key_Chain,
-      &key_value_pair->Key_values_per_thread_node
-    );
+  } else {
+    eno = EINVAL;
   }
 
-  return 0;
+  _Objects_Allocator_unlock();
+
+  return eno;
 }
 
 static int _POSIX_Keys_Delete_value(
-  pthread_key_t       key,
-  POSIX_Keys_Control *the_key,
-  RBTree_Node        *rb_node
+  pthread_key_t   key,
+  Thread_Control *executing
 )
 {
+  POSIX_Keys_Control *the_key;
+  int                 eno;
+
+  _Objects_Allocator_lock();
+
+  the_key = _POSIX_Keys_Get( key );
+  if ( the_key != NULL ) {
+    ISR_lock_Context  lock_context;
+    RBTree_Node      *node;
+
+    _POSIX_Keys_Key_value_acquire( executing, &lock_context );
 
-  if ( rb_node != NULL ) {
-    POSIX_Keys_Key_value_pair *key_value_pair =
-      POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( rb_node );
+    node = _POSIX_Keys_Key_value_find( key, executing );
+    if ( node != NULL ) {
+      POSIX_Keys_Key_value_pair *key_value_pair;
 
-    _POSIX_Keys_Free_key_value_pair( key_value_pair );
+      key_value_pair = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node );
+      _RBTree_Extract(
+        &executing->Keys.Key_value_pairs,
+        &key_value_pair->Lookup_node
+      );
+
+      _POSIX_Keys_Key_value_release( executing, &lock_context );
+
+      _POSIX_Keys_Key_value_free( key_value_pair );
+    } else {
+      _POSIX_Keys_Key_value_release( executing, &lock_context );
+    }
+
+    eno = 0;
+  } else {
+    eno = EINVAL;
   }
 
-  return 0;
+  _Objects_Allocator_unlock();
+
+  return eno;
 }
 
 /*
@@ -95,35 +132,28 @@ int pthread_setspecific(
   const void    *value
 )
 {
-  POSIX_Keys_Control *the_key;
-  Objects_Locations   location;
-  Thread_Control     *executing;
-  RBTree_Node        *rb_node;
-  int                 eno;
-
-  the_key = _POSIX_Keys_Get( key, &location );
-  switch ( location ) {
+  Thread_Control   *executing;
+  int               eno;
 
-    case OBJECTS_LOCAL:
-      executing = _Thread_Executing;
-      rb_node = _POSIX_Keys_Find( key, executing );
+  executing = _Thread_Get_executing();
 
-      if ( value != NULL ) {
-        eno = _POSIX_Keys_Set_value( key, value, the_key, executing, rb_node );
-      } else {
-        eno = _POSIX_Keys_Delete_value( key, the_key, rb_node );
-      }
+  if ( value != NULL ) {
+    ISR_lock_Context  lock_context;
+    RBTree_Node      *node;
 
-      _Objects_Put( &the_key->Object );
+    _POSIX_Keys_Key_value_acquire( executing, &lock_context );
 
-      return eno;
-
-#if defined(RTEMS_MULTIPROCESSING)
-    case OBJECTS_REMOTE:   /* should never happen */
-#endif
-    case OBJECTS_ERROR:
-      break;
+    node = _POSIX_Keys_Key_value_find( key, executing );
+    if ( node != NULL ) {
+      eno = _POSIX_Keys_Set_value( node, value );
+      _POSIX_Keys_Key_value_release( executing, &lock_context );
+    } else {
+      _POSIX_Keys_Key_value_release( executing, &lock_context );
+      eno = _POSIX_Keys_Create_value( key, value, executing );
+    }
+  } else {
+    eno = _POSIX_Keys_Delete_value( key, executing );
   }
 
-  return EINVAL;
+  return eno;
 }
diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h
index 44b706d7ff..4e0d8cf6f9 100644
--- a/cpukit/score/include/rtems/score/thread.h
+++ b/cpukit/score/include/rtems/score/thread.h
@@ -487,6 +487,21 @@ struct Thread_Action {
 };
 
 /**
+ * @brief Per-thread information for POSIX Keys.
+ */
+typedef struct {
+  /**
+   * @brief Key value pairs registered for this thread.
+   */
+  RBTree_Control Key_value_pairs;
+
+  /**
+   * @brief Lock to protect the tree operations.
+   */
+  ISR_LOCK_MEMBER( Lock )
+} Thread_Keys_information;
+
+/**
  * @brief Control block to manage thread actions.
  *
  * Use _Thread_Action_control_initialize() to initialize this structure.
@@ -837,13 +852,9 @@ struct _Thread_Control {
 #endif
 
   /**
-   * 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.
+   * @brief The POSIX Keys information.
    */
-  Chain_Control           Key_Chain;
+  Thread_Keys_information               Keys;
 
   /**
    * @brief Thread life-cycle control.
diff --git a/cpukit/score/src/threadinitialize.c b/cpukit/score/src/threadinitialize.c
index 0b5fd3a125..bcf03bf833 100644
--- a/cpukit/score/src/threadinitialize.c
+++ b/cpukit/score/src/threadinitialize.c
@@ -210,10 +210,9 @@ bool _Thread_Initialize(
 
   _Scheduler_Update_priority( the_thread, priority );
 
-  /*
-   * initialize thread's key vaule node chain
-   */
-  _Chain_Initialize_empty( &the_thread->Key_Chain );
+  /* POSIX Keys */
+  _RBTree_Initialize_empty( &the_thread->Keys.Key_value_pairs );
+  _ISR_lock_Initialize( &the_thread->Keys.Lock, "POSIX Key Value Pairs" );
 
   _Thread_Action_control_initialize( &the_thread->Post_switch_actions );
 
diff --git a/cpukit/score/src/threadrestart.c b/cpukit/score/src/threadrestart.c
index f5419741bf..155acaa8d1 100644
--- a/cpukit/score/src/threadrestart.c
+++ b/cpukit/score/src/threadrestart.c
@@ -97,6 +97,7 @@ static void _Thread_Free( Thread_Control *the_thread )
     _Objects_Get_information_id( the_thread->Object.id );
 
   _User_extensions_Thread_delete( the_thread );
+  _ISR_lock_Destroy( &the_thread->Keys.Lock );
   _Scheduler_Node_destroy( _Scheduler_Get( the_thread ), the_thread );
   _ISR_lock_Destroy( &the_thread->Timer.Lock );