[PATCH 1/2] posix: Reimplement POSIX Key manager to use a red-black tree.

[Gedare Bloom]

On Tue, Mar 12, 2013 at 8:34 PM, Gedare Bloom <gedare at rtems.org> wrote:
> From: Zhongwei Yao <ashi08104 at gmail.com>
>
> diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
> index 0bb1dbe..16aea78 100644
> --- a/cpukit/posix/include/rtems/posix/key.h
> +++ b/cpukit/posix/include/rtems/posix/key.h
> @@ -34,27 +37,53 @@ 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 chain node, which is
> +   * used in pre-allocated key node chain.
> +   */
> +  Chain_Node pre_ch_node;
Is a POSIX_Keys_Rbtree_node ever on two chains (one with ch_node and
one with pre_ch_node) at the same time?

If not, then they can share the same Chain_Control. This would also
eliminate the need below to use offsetof.

> diff --git a/cpukit/posix/src/keysetspecific.c b/cpukit/posix/src/keysetspecific.c
> index b25e44c..de96964 100644
> --- a/cpukit/posix/src/keysetspecific.c
> +++ b/cpukit/posix/src/keysetspecific.c
> @@ -37,18 +41,41 @@ 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;
> +  Chain_Node                  *ch_node;
> +  POSIX_API_Control           *api;
>
> -  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 );
> -      the_key->Values[ api ][ index ] = (void *) value;
> +      ch_node = _Chain_Get_unprotected( &_POSIX_Keys_Preallocation_chain );
What if the Preallocation chain is empty?

> +      /* there is no _Chain_Container_of in RTEMS Chain API */
> +      rb_node = ( POSIX_Keys_Rbtree_node * ) \
> +        ( ( uintptr_t )( ch_node ) \
> +          - offsetof( POSIX_Keys_Rbtree_node, pre_ch_node ) );
Might not need this if you share the chain node for the two chains. If
you do need to, maybe we should implement _Chain_Container_of().


>
> diff --git a/cpukit/sapi/include/confdefs.h b/cpukit/sapi/include/confdefs.h
> index cc55e92..2aaf30e 100644
> --- a/cpukit/sapi/include/confdefs.h
> +++ b/cpukit/sapi/include/confdefs.h
> @@ -1709,11 +1709,18 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
>
>    #ifndef CONFIGURE_MAXIMUM_POSIX_KEYS
>      #define CONFIGURE_MAXIMUM_POSIX_KEYS           0
> -    #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys) 0
> +    #define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS      0
> +    #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys, _key_pairs) 0
>    #else
> -    #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys) \
> +    #ifndef CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS
> +      #define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS \
> +        CONFIGURE_MAXIMUM_POSIX_KEYS \
> +        * (CONFIGURE_MAXIMUM_POSIX_THREADS + CONFIGURE_MAXIMUM_TASKS)
> +    #endif
> +  #define CONFIGURE_MEMORY_FOR_POSIX_KEYS(_keys, _key_pairs)       \
>        (_Configure_Object_RAM(_keys, sizeof(POSIX_Keys_Control) ) \
> -        + (_keys) * 3 * _Configure_From_workspace(sizeof(void *) * 2))
> +      + _key_pairs                        \
> +      * _Configure_From_workspace(sizeof(POSIX_Keys_Rbtree_node)))
>    #endif
Both CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS and
CONFIGURE_MAXIMUM_POSIX_KEYS should ignore the unlimited bit. Well,
the first should probably inherit it from either unlimited keys or
unlimited threads. The second should mask it off from _key_pairs by
_Configure_Max_Objects(_key_pairs).

We need to discuss the case of unlimited posix key pairs a little
further, because the pre-allocation strategy does not handle it
properly I think. The problem here is that a "key_pair" is not an
Object, and so it is not managed by the Object Manager, so it does not
make use of the pre-allocation support that Objects get. One approach
could be to wrap the pre-allocation of "key_pair" with the allocation
of keys themselves. This could easily handle limited and unlimited
keys with limited threads: allocate the number of keys * number of
threads every time Object allocation for keys occurs. The tricky case
is when threads is unlimited, in which case the Object allocation also
needs to allocate additional key_pairs when it allocates additional
threads.

-Gedare