[PATCH 1/2] posix: Reimplement POSIX Key manager to use a red-black tree.
Gedare Bloom
gedare at rtems.org
Sat Feb 23 14:38:26 UTC 2013
From: Zhongwei Yao <ashi08104 at gmail.com>
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.
---
cpukit/posix/include/rtems/posix/key.h | 54 ++++++++++++++++-----
cpukit/posix/include/rtems/posix/threadsup.h | 10 ++++
cpukit/posix/inline/rtems/posix/key.inl | 2 +-
cpukit/posix/src/key.c | 59 ++++++++++++++++++++++-
cpukit/posix/src/keycreate.c | 52 +-------------------
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 | 34 ++++++++++---
cpukit/posix/src/pthread.c | 3 +
cpukit/sapi/src/posixapi.c | 2 +-
12 files changed, 229 insertions(+), 112 deletions(-)
diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
index 0bb1dbe..f045dad 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,32 +37,57 @@ 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;
+ Objects_Control object;
+ /** 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.
*/
-void _POSIX_Key_Manager_initialization(void);
+void _POSIX_Keys_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.
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/inline/rtems/posix/key.inl b/cpukit/posix/inline/rtems/posix/key.inl
index ce5601b..9469580 100644
--- a/cpukit/posix/inline/rtems/posix/key.inl
+++ b/cpukit/posix/inline/rtems/posix/key.inl
@@ -45,7 +45,7 @@ RTEMS_INLINE_ROUTINE void _POSIX_Keys_Free (
POSIX_Keys_Control *the_key
)
{
- _Objects_Free( &_POSIX_Keys_Information, &the_key->Object );
+ _Objects_Free( &_POSIX_Keys_Information, &the_key->object );
}
/**
diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
index 6eace26..82c11af 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -29,6 +29,57 @@
#include <rtems/score/thread.h>
#include <rtems/score/wkspace.h>
#include <rtems/posix/key.h>
+#include <rtems/score/rbtree.h>
+
+/*
+ * _POSIX_Keys_Rbtree_compare_function
+ *
+ * DESCRIPTION:
+ * This routine compares the rbtree node
+ * by comparing POSIX key first and comparing thread id second.
+ * And 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.
+ *
+ * Input parameters: two rbtree node
+ *
+ * Output parameters: return positive if first node
+ * has higher key than second, negative if lower, 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;
+}
+
/*
* _POSIX_Key_Manager_initialization
@@ -42,7 +93,7 @@
* Output parameters: NONE
*/
-void _POSIX_Key_Manager_initialization(void)
+void _POSIX_Keys_Manager_initialization(void)
{
_Objects_Initialize_information(
&_POSIX_Keys_Information, /* object information table */
@@ -60,4 +111,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..09778c3 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,52 +48,8 @@ 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;
+ _Objects_Open_u32( &_POSIX_Keys_Information, &the_key->object, 0 );
+ *key = the_key->object.id;
_Thread_Enable_dispatch();
return 0;
}
diff --git a/cpukit/posix/src/keydelete.c b/cpukit/posix/src/keydelete.c
index 5ef6261..3f594bd 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..e01e6e9 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..39c0fcc 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..db31d2b 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..132061a 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,36 @@ 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() would call _Thread_Disable_dispatch() implicitly*/
+ _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;
}
diff --git a/cpukit/sapi/src/posixapi.c b/cpukit/sapi/src/posixapi.c
index 3f65442..b5e62c2 100644
--- a/cpukit/sapi/src/posixapi.c
+++ b/cpukit/sapi/src/posixapi.c
@@ -64,7 +64,7 @@ void _POSIX_API_Initialize(void)
_POSIX_signals_Manager_Initialization();
_POSIX_Threads_Manager_initialization();
_POSIX_Condition_variables_Manager_initialization();
- _POSIX_Key_Manager_initialization();
+ _POSIX_Keys_Manager_initialization();
_POSIX_Mutex_Manager_initialization();
_POSIX_Message_queue_Manager_initialization();
_POSIX_Semaphore_Manager_initialization();
--
1.7.1
More information about the devel
mailing list