[PATCH 2/2] posix: Reimplement POSIX Key manager to use a red-black tree.
Gedare Bloom
gedare at rtems.org
Fri Feb 8 02:20:44 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 | 56 ++++++++++++++++-----
cpukit/posix/include/rtems/posix/threadsup.h | 4 ++
cpukit/posix/inline/rtems/posix/key.inl | 2 +-
cpukit/posix/src/key.c | 52 +++++++++++++++++++-
cpukit/posix/src/keycreate.c | 53 +-------------------
cpukit/posix/src/keydelete.c | 4 +-
cpukit/posix/src/keyfreememory.c | 35 ++++++++++++-
cpukit/posix/src/keygetspecific.c | 21 +++++---
cpukit/posix/src/keyrundestructors.c | 68 +++++++++++++++-----------
cpukit/posix/src/keysetspecific.c | 32 +++++++++---
cpukit/posix/src/pthread.c | 3 +
cpukit/sapi/src/posixapi.c | 2 +-
12 files changed, 216 insertions(+), 116 deletions(-)
diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
index 0bb1dbe..80e534b 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 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 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;
/**
- * The following defines the information control block used to manage
- * this class of objects.
+ * @brief The data structure used to manage a POSIX key.
+ */
+typedef struct {
+ /** This field is the Object control structure. */
+ Objects_Control object;
+ /** This field is the data destructor. */
+ void (*destructor) (void *);
+ } POSIX_Keys_Control;
+
+/**
+ * @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..f47a7d4 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
@@ -78,6 +79,9 @@ typedef struct {
int cancelation_requested;
/** This is the set of cancelation handlers. */
Chain_Control Cancellation_Handlers;
+
+ /** This is the thread key value chain's control */
+ Chain_Control the_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..b0a1f86 100644
--- a/cpukit/posix/src/key.c
+++ b/cpukit/posix/src/key.c
@@ -29,6 +29,49 @@
#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 +85,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 +103,11 @@ void _POSIX_Key_Manager_initialization(void)
NULL /* Proxy extraction support callout */
#endif
);
+
+ _RBTree_Initialize_empty(
+ &_POSIX_Keys_Rbtree, /* the rbtree control block */
+ _POSIX_Keys_Rbtree_compare_function,
+ /* the rbtree compare function */
+ true /* true if each rbtree node is unique */
+ );
}
diff --git a/cpukit/posix/src/keycreate.c b/cpukit/posix/src/keycreate.c
index b41b590..84a4d9c 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,9 @@ 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;
+ /*problem: not clear about _Objects_Open_u32() */
+ _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..f45e264 100644
--- a/cpukit/posix/src/keydelete.c
+++ b/cpukit/posix/src/keydelete.c
@@ -42,9 +42,9 @@ int pthread_key_delete(
switch ( location ) {
case OBJECTS_LOCAL:
- _Objects_Close( &_POSIX_Keys_Information, &the_key->Object );
-
_POSIX_Keys_Free_memory( the_key );
+ /* problem: should it done before _POSIX_Keys_Free_memory? */
+ _Objects_Close( &_POSIX_Keys_Information, &the_key->object );
/*
* NOTE: The destructor is not called and it is the responsibility
diff --git a/cpukit/posix/src/keyfreememory.c b/cpukit/posix/src/keyfreememory.c
index f71af4f..50f560e 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..61adea6 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,23 @@ 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 ];
+ /** TODO: search the node in TCB's chain(maybe the rbtree) to speed up the search */
+ 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..687217c 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,43 @@ 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();
+
+ chain = &((POSIX_API_Control *)thread->API_Extensions[ THREAD_API_POSIX ])->the_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 );
- done = true;
-
- for ( index = 1 ; index <= max ; ++index ) {
- POSIX_Keys_Control *key = (POSIX_Keys_Control *)
- _POSIX_Keys_Information.local_table [ index ];
-
- 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;
- }
- }
- }
+ /**
+ * 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();
+
+ _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..eeb4d84 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,34 @@ 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->the_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..22c835f 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->the_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