[PATCH 1/2] posix: Reimplement POSIX Key manager to use a red-black tree.
Ashi
ashi08104 at gmail.com
Fri Apr 19 15:50:23 UTC 2013
Hi, all, as Gedare pointed out in previous post, the solution in this patch
*can't* support unlimited POSIX Key well(it's exactly the case when
unlimited mode enabled). After some discussion, I come up with a new
solution, which can support unlimited mode, but also with some defect.
The idea is:
put all memory allocation work in POSIX Key manager to Object Manager, then
we needn't allocate memory from workspace when each key value create, which
is very similar to the pre-allocation approach in this patch and the other
important benefit is since the memory allocation is managed by Object
Manager, it can support unlimited mode automatically.
And to the management of key value, let pthread_key_t type be a chain head,
which keeps track of value within that key and then set_specific()
operation in POSIX Key can iterate this chain to find specific key value.
However, this can be a problem when a key is used by many threads at same
time(say n threads for example), in which worst case the runtime of
set_specific() is O(n) and another concern is the memory overhead. Because
every key value is associated with one Objects_control structure.
Do you have any suggestion to this idea? Is the unlimited mode very
important for POSIX Key? Thanks for any reply! And If necessary, I can add
more details.
Best regards,
Zhongwei
On Mon, Mar 18, 2013 at 10:08 PM, Ashi <ashi08104 at gmail.com> wrote:
> Hi, Gedare, I think Joel has mentioned this about unlimited problem. I
> remember Joel has suggested a way to deal with this when use the
> pre-allocation approach. But I haven't got that idea... However, I only
> find my problem description mail, haven't found Joel's solution... Joel, do
> you remember there is such a mail?
> "
> >Joel wrote:
> >>9/12/2012 5:08 AM, Ashi wrote:
> >>Hi, Joel.
> >>My work stops at the problem of how to support unlimited mode when we
> pre-allocate all memory at key manager >>initialization, and I still
> haven't got time to learn the object extend code sample as Chris mentioned
> in last mail. And I >>also haven't figured out how to write right
> Configuration in confdef.h, my last post in dev-list is about this.
> >>I really have a busy time these days, and really sorry for my slow
> progress. Anyway I'll try my best!
> >I think it should be merged as it is. When in unlimited mode, we can
> document the
> >recommendation that you use a unified work space. We can leave this as a
> >future enhancement.
>
> >But what you did is a BIG improvement. This next step is an integration
> clean up
> >that can occur separately.
>
> >let's move to review and merge what you have, update the project page,
> check coverage
> >on what's there, etc.
> "
>
> On Fri, Mar 15, 2013 at 6:53 AM, Gedare Bloom <gedare at rtems.org> wrote:
>
>> 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
>>
> Cheers,
> Zhongwei
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130419/51e2d906/attachment.html>
More information about the devel
mailing list