[PATCH 1/2] posix: Reimplement POSIX Key manager to use a red-black tree.
Joel Sherrill
Joel.Sherrill at OARcorp.com
Sat Feb 23 14:52:17 UTC 2013
Some quick comments. Reviewing on my Nexus 7 and I would love a client that let's you respond inline.
Object field in the data structure should be named with capitalization.
Look for "DESCRIPTION". convert this and similar blocks to Doxygen.
Why was the manager initialization method renamed keys manager initialization? Others are singular.
New files should follow style with @file comment block.
No need for comment about disable dispatching above call to Get to convert from Id to pointer.
Gedare Bloom <gedare at rtems.org> wrote:
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
_______________________________________________
rtems-devel mailing list
rtems-devel at rtems.org
http://www.rtems.org/mailman/listinfo/rtems-devel
More information about the devel
mailing list