[PATCH] posix: Reimplement POSIX Key manager to use a red-black tree.
Ashi
ashi08104 at gmail.com
Fri Aug 2 01:03:40 UTC 2013
Hi, Sebastian, thanks for your helpful review!
On Thu, Aug 1, 2013 at 3:53 PM, Sebastian Huber <
sebastian.huber at embedded-brains.de> wrote:
> Hello Ashi,
>
> thanks for your update.
>
> On 2013-07-31 15:03, Ashi wrote:
>
>> diff --git a/cpukit/posix/include/rtems/**posix/config.h
>> b/cpukit/posix/include/rtems/**posix/config.h
>> index 104bd84..2c76cc1 100644
>> --- a/cpukit/posix/include/rtems/**posix/config.h
>> +++ b/cpukit/posix/include/rtems/**posix/config.h
>> @@ -51,6 +51,7 @@ typedef struct {
>> uint32_t maximum_mutexes;
>> uint32_t maximum_condition_variables;
>> uint32_t maximum_keys;
>> + uint32_t maximum_key_pairs;
>>
>
> I would call this maximum_key_value_pairs.
> uint32_t maximum_timers;
>> uint32_t maximum_queued_signals;
>> uint32_t maximum_message_queues;
>> diff --git a/cpukit/posix/include/rtems/**posix/key.h
>> b/cpukit/posix/include/rtems/**posix/key.h
>> index 6d2ebff..d2c51bd 100644
>> --- a/cpukit/posix/include/rtems/**posix/key.h
>> +++ b/cpukit/posix/include/rtems/**posix/key.h
>> @@ -1,6 +1,6 @@
>> /**
>> * @file
>> - *
>> + *
>> * @brief POSIX Key Private Support
>> *
>> * This include file contains all the private support information for
>> @@ -8,24 +8,30 @@
>> */
>>
>> /*
>> - * COPYRIGHT (c) 1989-2011.
>> - * On-Line Applications Research Corporation (OAR).
>> + * Copyright (c) 2012 Zhongwei Yao.
>> + * COPYRIGHT (c) 1989-2011.
>> + * 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.com/license/**LICENSE<http://www.rtems.com/license/LICENSE>
>> .
>> + * The license and distribution terms for this file may be
>> + * found in the file LICENSE in this distribution or at
>> + *http://www.rtems.com/license/**LICENSE<http://www.rtems.com/license/LICENSE>
>> .
>> */
>>
>> #ifndef _RTEMS_POSIX_KEY_H
>> #define _RTEMS_POSIX_KEY_H
>>
>> +#include <rtems/score/object.h>
>> +#include <rtems/score/rbtree.h>
>> +#include <rtems/score/chain.h>
>> +#include <rtems/score/chainimpl.h>
>> +#include <rtems/score/freechain.h>
>> #include <rtems/score/objectimpl.h>
>>
>
> The xyzimpl.h files include the zyz.h files. So the object.h and chain.h
> includes are superfluous.
>
>
>> /**
>> * @defgroup POSIX_KEY POSIX Key
>> *
>> * @ingroup POSIXAPI
>> - *
>> + *
>> */
>> /**@{**/
>>
>> @@ -34,40 +40,93 @@ 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.
>> + * Forward declaretion
>> + */
>> +typedef struct POSIX_Keys_Freechain_node_**struct
>> POSIX_Keys_Freechain_node;
>> +
>> +/**
>> + * @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;
>>
>
> It would be nice to have field names that describe the purpose of the
> nodes, e.g. Key_values_per_thread_node and Key_value_lookup_node.
>
> + /** This field points to parent freechain node */
>> + POSIX_Keys_Freechain_node *fc_node_ptr;
>>
>
> I don't think we need this fc_node_ptr.
>
Do you mean use a 'Container' macro instead?
>
> + /** 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;
>>
>
> I would call this POSIX_Keys_Key_value_pair.
>
> +
>> +/**
>> + * @brief POSIX_Keys_Freechain is used in Freechain structure
>> + */
>> +typedef struct {
>> + Freechain_Control super_fc;
>> + size_t bump_count;
>> +} POSIX_Keys_Freechain;
>> +
>> +/**
>> + * @brief POSIX_Keys_Freechain_node is freechain node
>> + */
>> +struct POSIX_Keys_Freechain_node_**struct {
>> + Chain_Node ch_node;
>> + POSIX_Keys_Rbtree_node rb_node;
>> +};
>>
>
> Why not use POSIX_Keys_Rbtree_node directly?
>
Since every freechain node needs a Chain_Node in its first field. There is
a Chain_Node in POSIX_Keys_Rbtree_node, but it is used in each thread's
key value chain. So I add a Chain_Node to 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 POSIX keys manager initialization.
>> + * @brief The rbtree control block used to manage all key values
>> + */
>> +POSIX_EXTERN RBTree_Control _POSIX_Keys_Rbtree;
>>
>
> I would call this _POSIX_Keys_Key_value_lookup_**tree.
>
> [...]
>
>> diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
>> index 6eace26..71d6a8d 100644
>> --- a/cpukit/posix/src/key.c
>> +++ b/cpukit/posix/src/key.c
>> @@ -6,12 +6,13 @@
>> */
>>
>> /*
>> - * COPYRIGHT (c) 1989-2008.
>> - * On-Line Applications Research Corporation (OAR).
>> + * Copyright (c) 2012 Zhongwei Yao.
>> + * COPYRIGHT (c) 1989-2008.
>> + * 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.com/license/**LICENSE<http://www.rtems.com/license/LICENSE>
>> .
>> + * The license and distribution terms for this file may be
>> + * found in the file LICENSE in this distribution or at
>> + *http://www.rtems.com/license/**LICENSE<http://www.rtems.com/license/LICENSE>
>> .
>> */
>>
>> #if HAVE_CONFIG_H
>> @@ -29,19 +30,116 @@
>> #include <rtems/score/thread.h>
>> #include <rtems/score/wkspace.h>
>> #include <rtems/posix/key.h>
>> +#include <rtems/score/rbtree.h>
>> +#include <rtems/score/chain.h>
>> +#include <rtems/score/freechain.h>
>>
>> -/*
>> - * _POSIX_Key_Manager_**initialization
>> - *
>> - * DESCRIPTION:
>> - *
>> - * This routine performs the initialization necessary for this manager.
>> +/* forward declarations to avoid warnings */
>> +void _POSIX_Keys_Keypool_init(void)**;
>> +bool _POSIX_Keys_Freechain_extend(**Freechain_Control *freechain);
>> +void _POSIX_Keys_Freechain_init(**Freechain_Control *freechain);
>>
>
> Never place declarations of global functions in a source file.
>
> [...]
>
>> + /**
>> + * 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 );
>> + /* append the node to _POSIX_Keys_Keypool */
>> + _Freechain_Put( (Freechain_Control *)&_POSIX_Keys_Keypool,
>> + ( void * ) p->fc_node_ptr);
>>
> [...]
>
> Please avoid casts like this. Use _Freechain_Put(
> &_POSIX_Keys_Keypool.super_fc, ...) instead.
>
>
> --
> Sebastian Huber, embedded brains GmbH
>
> Address : Dornierstr. 4, D-82178 Puchheim, Germany
> Phone : +49 89 189 47 41-16
> Fax : +49 89 189 47 41-09
> E-Mail : sebastian.huber at embedded-**brains.de<sebastian.huber at embedded-brains.de>
> PGP : Public key available on request.
>
> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
>
Thanks,
Zhongwei
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130802/d0d6d300/attachment-0001.html>
More information about the devel
mailing list