From 5eaf0e7458bac80ba669f03c4feaae5bad55c6c9 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Thu, 17 Mar 2016 07:56:31 +0100 Subject: posix: Use per-thread lookup tree for POSIX Keys Yields higher performance on SMP systems. Close #2625. --- cpukit/posix/src/key.c | 140 ++++++++++---------------------- cpukit/posix/src/keycreate.c | 12 +-- cpukit/posix/src/keydelete.c | 67 +++++++++------- cpukit/posix/src/keyfreememory.c | 60 -------------- cpukit/posix/src/keygetspecific.c | 50 ++++-------- cpukit/posix/src/keysetspecific.c | 164 ++++++++++++++++++++++---------------- 6 files changed, 200 insertions(+), 293 deletions(-) delete mode 100644 cpukit/posix/src/keyfreememory.c (limited to 'cpukit/posix/src') 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 #include -#include -#include #include #include 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 -#include -#include -#include - -#include -#include -#include #include +#include + /** * 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 + #include -#include -#include -#include -#include -#include -#include -#include +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 -#include - -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 -#include -#include -#include - -#include -#include -#include -#include #include /* @@ -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 -#include -#include #include -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; } -- cgit v1.2.3