[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.html>


More information about the devel mailing list