posix: Use per-thread lookup tree for POSIX Keys

Yields higher performance on SMP systems.

Close #2625.

6 files changed, 200 insertions, 293 deletions

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;
 }