[PATCH 1/3] The POSIX Key manager is reimplemented with a red-black tree to store the keys and values. This code was contributed as part of GSOC 2012.
Gedare Bloom
gedare at rtems.org
Tue Mar 5 20:56:11 UTC 2013
I have to test this code, and still need to fix the confdefs issue. I
just wanted to document where it is at right now. The confdefs would
be a separate patch to add on.
On Tue, Mar 5, 2013 at 3:55 PM, Gedare Bloom <gedare at rtems.org> wrote:
> From: Zhongwei Yao <ashi08104 at gmail.com>
>
> ---
> cpukit/posix/include/rtems/posix/key.h | 50 +++++++++++++++----
> cpukit/posix/include/rtems/posix/threadsup.h | 10 ++++
> cpukit/posix/src/key.c | 63 +++++++++++++++++++++---
> cpukit/posix/src/keycreate.c | 48 ------------------
> cpukit/posix/src/keydelete.c | 3 +-
> cpukit/posix/src/keyfreememory.c | 35 ++++++++++++-
> cpukit/posix/src/keygetspecific.c | 20 +++++---
> cpukit/posix/src/keyrundestructors.c | 67 +++++++++++++++----------
> cpukit/posix/src/keysetspecific.c | 33 ++++++++++---
> cpukit/posix/src/pthread.c | 3 +
> 10 files changed, 219 insertions(+), 113 deletions(-)
>
> diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
> index 0bb1dbe..ab1fe04 100644
> --- a/cpukit/posix/include/rtems/posix/key.h
> +++ b/cpukit/posix/include/rtems/posix/key.h
> @@ -8,6 +8,7 @@
> */
>
> /*
> + * Copyright (c) 2012 Zhongwei Yao.
> * COPYRIGHT (c) 1989-2011.
> * On-Line Applications Research Corporation (OAR).
> *
> @@ -20,6 +21,8 @@
> #define _RTEMS_POSIX_KEY_H
>
> #include <rtems/score/object.h>
> +#include <rtems/score/rbtree.h>
> +#include <rtems/score/chain.h>
>
> /**
> * @defgroup POSIX_KEY POSIX Key
> @@ -34,27 +37,42 @@ extern "C" {
> #endif
>
> /**
> - * This is the data Structure used to manage a POSIX key.
> - *
> - * NOTE: The Values is a table indexed by the index portion of the
> - * ID of the currently executing thread.
> + * @brief The rbtree node used to manage a POSIX key and value.
> + */
> +typedef struct {
> + /** This field is the chain node structure. */
> + Chain_Node ch_node;
> + /** This field is the rbtree node structure. */
> + RBTree_Node rb_node;
> + /** This field is the POSIX key used as an rbtree key */
> + pthread_key_t key;
> + /** This field is the Thread id also used as an rbtree key */
> + Objects_Id thread_id;
> + /** This field points to the POSIX key value of specific thread */
> + void *value;
> + } POSIX_Keys_Rbtree_node;
> +
> +/**
> + * @brief The data structure used to manage a POSIX key.
> */
> typedef struct {
> /** This field is the Object control structure. */
> Objects_Control Object;
> - /** This field points to the optional destructor method. */
> - void (*destructor)( void * );
> - /** This field points to the values per thread. */
> - void **Values[ OBJECTS_APIS_LAST + 1 ];
> -} POSIX_Keys_Control;
> + /** This field is the data destructor. */
> + void (*destructor) (void *);
> + } POSIX_Keys_Control;
>
> /**
> - * The following defines the information control block used to manage
> - * this class of objects.
> + * @brief The information control block used to manage this class of objects.
> */
> POSIX_EXTERN Objects_Information _POSIX_Keys_Information;
>
> /**
> + * @brief The rbtree control block used to manage all key values
> + */
> +POSIX_EXTERN RBTree_Control _POSIX_Keys_Rbtree;
> +
> +/**
> * @brief POSIX keys manager initialization.
> *
> * This routine performs the initialization necessary for this manager.
> @@ -62,6 +80,16 @@ POSIX_EXTERN Objects_Information _POSIX_Keys_Information;
> void _POSIX_Key_Manager_initialization(void);
>
> /**
> + * @brief POSIX keys Red-Black tree node comparison.
> + *
> + * This routine compares the rbtree node
> + */
> +int _POSIX_Keys_Rbtree_compare_function(
> + const RBTree_Node *node1,
> + const RBTree_Node *node2
> +);
> +
> +/**
> * @brief Create thread-specific data POSIX key.
> *
> * This function executes all the destructors associated with the thread's
> diff --git a/cpukit/posix/include/rtems/posix/threadsup.h b/cpukit/posix/include/rtems/posix/threadsup.h
> index 80f64dc..d746ea8 100644
> --- a/cpukit/posix/include/rtems/posix/threadsup.h
> +++ b/cpukit/posix/include/rtems/posix/threadsup.h
> @@ -21,6 +21,7 @@
> #include <sys/signal.h>
> #include <rtems/score/coresem.h>
> #include <rtems/score/tqdata.h>
> +#include <rtems/score/chain.h>
>
> /**
> * @defgroup POSIX_THREAD POSIX Thread API Extension
> @@ -79,6 +80,15 @@ typedef struct {
> /** This is the set of cancelation handlers. */
> Chain_Control Cancellation_Handlers;
>
> + /**
> + * This is the thread key value chain's control, which is used
> + * to track all key value for specific thread, and when thread
> + * exits, we can remove all key value for specific thread by
> + * iterating this chain, or we have to search a whole rbtree,
> + * which is inefficient.
> + */
> + Chain_Control Key_Chain;
> +
> } POSIX_API_Control;
>
> /**
> diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
> index 6eace26..177543d 100644
> --- a/cpukit/posix/src/key.c
> +++ b/cpukit/posix/src/key.c
> @@ -29,17 +29,58 @@
> #include <rtems/score/thread.h>
> #include <rtems/score/wkspace.h>
> #include <rtems/posix/key.h>
> +#include <rtems/score/rbtree.h>
>
> -/*
> - * _POSIX_Key_Manager_initialization
> - *
> - * DESCRIPTION:
> - *
> - * This routine performs the initialization necessary for this manager.
> +/**
> + * @brief This routine compares the rbtree node by comparing POSIX key first
> + * and comparing thread id second.
> *
> - * Input parameters: NONE
> + * if either of the input nodes's thread_id member is 0, then it will only
> + * compare the pthread_key_t member. That is when we pass thread_id = 0 node
> + * as a search node, the search is done only by pthread_key_t.
> *
> - * Output parameters: NONE
> + * @param[in] node1 The node to be compared *
> + * @param[in] node2 The node to be compared
> + * @retval positive if first node has higher key than second
> + * @retval negative if lower
> + * @retval 0 if equal,and for all the thread id is unique, then return 0 is
> + * impossible
> + */
> +
> +int _POSIX_Keys_Rbtree_compare_function(
> + const RBTree_Node *node1,
> + const RBTree_Node *node2
> +)
> +{
> + pthread_key_t key1 = _RBTree_Container_of(node1,
> + POSIX_Keys_Rbtree_node,
> + rb_node)->key;
> + pthread_key_t key2 = _RBTree_Container_of(node2,
> + POSIX_Keys_Rbtree_node,
> + rb_node)->key;
> +
> + Objects_Id thread_id1 = _RBTree_Container_of(node1,
> + POSIX_Keys_Rbtree_node,
> + rb_node)->thread_id;
> + Objects_Id thread_id2 = _RBTree_Container_of(node2,
> + POSIX_Keys_Rbtree_node,
> + rb_node)->thread_id;
> +
> + int diff = key1 - key2;
> + if ( diff )
> + return diff;
> + /**
> + * if thread_id1 or thread_id2 equals to 0, only key1 and key2 is valued.
> + * it enables us search node only by pthread_key_t type key.
> + */
> + if ( thread_id1 && thread_id2 )
> + return thread_id1 - thread_id2;
> + return 0;
> +}
> +
> +
> +/**
> + * @brief This routine performs the initialization necessary for this manager.
> */
>
> void _POSIX_Key_Manager_initialization(void)
> @@ -60,4 +101,10 @@ void _POSIX_Key_Manager_initialization(void)
> NULL /* Proxy extraction support callout */
> #endif
> );
> +
> + _RBTree_Initialize_empty(
> + &_POSIX_Keys_Rbtree,
> + _POSIX_Keys_Rbtree_compare_function,
> + true
> + );
> }
> diff --git a/cpukit/posix/src/keycreate.c b/cpukit/posix/src/keycreate.c
> index b41b590..2d31d86 100644
> --- a/cpukit/posix/src/keycreate.c
> +++ b/cpukit/posix/src/keycreate.c
> @@ -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 5ef6261..ae15b7f 100644
> --- a/cpukit/posix/src/keydelete.c
> +++ b/cpukit/posix/src/keydelete.c
> @@ -42,8 +42,6 @@ int pthread_key_delete(
> switch ( location ) {
>
> case OBJECTS_LOCAL:
> - _Objects_Close( &_POSIX_Keys_Information, &the_key->Object );
> -
> _POSIX_Keys_Free_memory( the_key );
>
> /*
> @@ -51,6 +49,7 @@ int pthread_key_delete(
> * of the application to free the memory.
> */
> _POSIX_Keys_Free( the_key );
> + _Objects_Close( &_POSIX_Keys_Information, &the_key->Object );
> _Thread_Enable_dispatch();
> return 0;
>
> diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
> index f71af4f..5f7764b 100644
> --- a/cpukit/posix/src/keyfreememory.c
> +++ b/cpukit/posix/src/keyfreememory.c
> @@ -21,14 +21,43 @@
> #include <rtems/system.h>
> #include <rtems/score/thread.h>
> #include <rtems/score/wkspace.h>
> +#include <rtems/score/rbtree.h>
> #include <rtems/posix/key.h>
>
> void _POSIX_Keys_Free_memory(
> POSIX_Keys_Control *the_key
> )
> {
> - uint32_t the_api;
> + POSIX_Keys_Rbtree_node search_node;
> + POSIX_Keys_Rbtree_node *p;
> + RBTree_Node *iter, *next;
>
> - for ( the_api = 1; the_api <= OBJECTS_APIS_LAST; the_api++ )
> - _Workspace_Free( the_key->Values[ the_api ] );
> + search_node.key = the_key->Object.id;
> + search_node.thread_id = 0;
> + iter = _RBTree_Find_unprotected( &_POSIX_Keys_Rbtree, &search_node.rb_node);
> + if ( !iter )
> + return;
> + /**
> + * find the smallest thread_id node in the rbtree.
> + */
> + next = _RBTree_Next_unprotected( iter, RBT_LEFT );
> + p = _RBTree_Container_of( next, POSIX_Keys_Rbtree_node, rb_node );
> + while ( p->key == the_key->Object.id) {
> + iter = next;
> + next = _RBTree_Next_unprotected( iter, RBT_LEFT );
> + p = _RBTree_Container_of( next, POSIX_Keys_Rbtree_node, rb_node );
> + }
> +
> + /**
> + * delete all nodes belongs to the_key from the rbtree and chain.
> + */
> + p = _RBTree_Container_of( iter, POSIX_Keys_Rbtree_node, rb_node );
> + while ( p->key == the_key->Object.id ) {
> + next = _RBTree_Next_unprotected( iter, RBT_RIGHT );
> + _RBTree_Extract_unprotected( &_POSIX_Keys_Rbtree, iter );
> + _Chain_Extract_unprotected( &p->ch_node );
> + _Workspace_Free( p );
> + iter = next;
> + p = _RBTree_Container_of( iter, POSIX_Keys_Rbtree_node, rb_node );
> + }
> }
> diff --git a/cpukit/posix/src/keygetspecific.c b/cpukit/posix/src/keygetspecific.c
> index debad83..eafa0ea 100644
> --- a/cpukit/posix/src/keygetspecific.c
> +++ b/cpukit/posix/src/keygetspecific.c
> @@ -26,6 +26,7 @@
> #include <rtems/system.h>
> #include <rtems/score/thread.h>
> #include <rtems/score/wkspace.h>
> +#include <rtems/score/rbtree.h>
> #include <rtems/posix/key.h>
>
> /*
> @@ -36,19 +37,24 @@ void *pthread_getspecific(
> pthread_key_t key
> )
> {
> - register POSIX_Keys_Control *the_key;
> - uint32_t api;
> - uint32_t index;
> Objects_Locations location;
> + POSIX_Keys_Rbtree_node search_node;
> + RBTree_Node *p;
> void *key_data;
>
> - the_key = _POSIX_Keys_Get( key, &location );
> + _POSIX_Keys_Get( key, &location );
> switch ( location ) {
>
> case OBJECTS_LOCAL:
> - api = _Objects_Get_API( _Thread_Executing->Object.id );
> - index = _Objects_Get_index( _Thread_Executing->Object.id );
> - key_data = (void *) the_key->Values[ api ][ index ];
> + search_node.key = key;
> + search_node.thread_id = _Thread_Executing->Object.id;
> + p = _RBTree_Find_unprotected( &_POSIX_Keys_Rbtree, &search_node.rb_node);
> + key_data = NULL;
> + if ( p ) {
> + key_data = _RBTree_Container_of( p,
> + POSIX_Keys_Rbtree_node,
> + rb_node )->value;
> + }
> _Thread_Enable_dispatch();
> return key_data;
>
> diff --git a/cpukit/posix/src/keyrundestructors.c b/cpukit/posix/src/keyrundestructors.c
> index 9f48888..a6e1090 100644
> --- a/cpukit/posix/src/keyrundestructors.c
> +++ b/cpukit/posix/src/keyrundestructors.c
> @@ -23,7 +23,10 @@
> #include <rtems/system.h>
> #include <rtems/score/object.h>
> #include <rtems/score/thread.h>
> +#include <rtems/score/wkspace.h>
> +#include <rtems/score/chain.h>
> #include <rtems/posix/key.h>
> +#include <rtems/posix/threadsup.h>
>
> /*
> * _POSIX_Keys_Run_destructors
> @@ -38,36 +41,46 @@ 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_Rbtree_node *,
> + * because Chain_Node is the first member of POSIX_Keys_Rbtree_node
> + * structure.
> + */
> + _RBTree_Extract_unprotected( &_POSIX_Keys_Rbtree,
> + &((POSIX_Keys_Rbtree_node *)iter)->rb_node );
> + _Chain_Extract_unprotected( iter );
>
> - 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_Rbtree_node *)iter)->key,
> + &location);
> + destructor = the_key->destructor;
> + value = ((POSIX_Keys_Rbtree_node *)iter)->value;
> + if ( destructor != NULL && value != NULL )
> + (*destructor)( value );
> + /**
> + * disable dispatch is nested here
> + */
> + _Thread_Enable_dispatch();
>
> - if ( key != NULL && key->destructor != NULL ) {
> - void *value = key->Values [ thread_api ][ thread_index ];
> -
> - if ( value != NULL ) {
> - key->Values [ thread_api ][ thread_index ] = NULL;
> - (*key->destructor)( value );
> - done = false;
> - }
> - }
> - }
> + _Workspace_Free( (POSIX_Keys_Rbtree_node *)iter );
> + iter = next;
> }
> + _Thread_Enable_dispatch();
> }
> diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
> index b25e44c..eae1917 100644
> --- a/cpukit/posix/src/keysetspecific.c
> +++ b/cpukit/posix/src/keysetspecific.c
> @@ -26,7 +26,9 @@
> #include <rtems/system.h>
> #include <rtems/score/thread.h>
> #include <rtems/score/wkspace.h>
> +#include <rtems/score/rbtree.h>
> #include <rtems/posix/key.h>
> +#include <rtems/posix/threadsup.h>
>
> /*
> * 17.1.2 Thread-Specific Data Management, P1003.1c/Draft 10, p. 165
> @@ -37,18 +39,35 @@ int pthread_setspecific(
> const void *value
> )
> {
> - register POSIX_Keys_Control *the_key;
> - uint32_t api;
> - uint32_t index;
> Objects_Locations location;
> + POSIX_Keys_Rbtree_node *rb_node;
> + 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;
> + rb_node = _Workspace_Allocate( sizeof( POSIX_Keys_Rbtree_node ) );
> + if ( !rb_node ) {
> + _Thread_Enable_dispatch();
> + return ENOMEM;
> + }
> +
> + rb_node->key = key;
> + rb_node->thread_id = _Thread_Executing->Object.id;
> + rb_node->value = value;
> + if (_RBTree_Insert_unprotected( &_POSIX_Keys_Rbtree,
> + &(rb_node->rb_node) ) ) {
> + _Workspace_Free( rb_node );
> + _Thread_Enable_dispatch();
> + return EAGAIN;
> + }
> +
> + /** append rb_node to the thread API extension's chain */
> + api = (POSIX_API_Control *)\
> + (_Thread_Executing->API_Extensions[THREAD_API_POSIX]);
> + _Chain_Append_unprotected( &api->Key_Chain, &rb_node->ch_node );
> +
> _Thread_Enable_dispatch();
> return 0;
>
> diff --git a/cpukit/posix/src/pthread.c b/cpukit/posix/src/pthread.c
> index 873449a..0ea44f1 100644
> --- a/cpukit/posix/src/pthread.c
> +++ b/cpukit/posix/src/pthread.c
> @@ -234,6 +234,9 @@ static bool _POSIX_Threads_Create_extension(
> created
> );
>
> + /** initialize thread's key vaule node chain */
> + _Chain_Initialize_empty( &api->Key_Chain );
> +
> return true;
> }
>
> --
> 1.7.1
>
More information about the devel
mailing list