POSIX key structure in rbtree approach

Gedare Bloom gedare at rtems.org
Tue May 8 15:06:07 UTC 2012 

On Tue, May 8, 2012 at 3:17 AM, Ashi <ashi08104 at gmail.com> wrote:
>
>
> 2012/5/7 Gedare Bloom <gedare at rtems.org>
>>
>> On Mon, May 7, 2012 at 11:16 AM, Ashi <ashi08104 at gmail.com> wrote:
>> > I'm terribly sorry for my late reply. I'm off for my weekend.
>> >
>> Most of us are. :)
>>
>> > 2012/5/4 Gedare Bloom <gedare at rtems.org>
>> >>
>> >> On Fri, May 4, 2012 at 3:28 AM, Ashi <ashi08104 at gmail.com> wrote:
>> >> > Hi, all. I'm working on the "Use hash or map in POSIX keys" project.
>> >> > As Joel said, the first thing to be determined is the problem of what
>> >> > data goes with each thread and what goes with each key. I find it's
>> >> > difficult to design the interface without some specific approach. And
>> >> > since the rbtree api is available in RTEMS, I have tried to do the
>> >> > design in the rbtree approach.
>> >> >
>> >> Good. The rbtree should support an efficient map operation.
>> >>
>> > Gedare, thanks for your reply!
>> >
>> >>
>> >> > I find 2 data structures need revised(added): POSIX_Keys_Control and
>> >> > key_node.
>> >> >
>> >> > typedef struct {
>> >> >            Objects_Control     Object;
>> >> >            void     (*destructor)( void * );
>> >> >            key_node * key_node_ptr;
>> >> > }POSIX_Keys_Control;
>> >> >
>> >> > typedef struct{
>> >> >          rtems_rbtree_node Node;
>> >> >          Objects_Id thread_id;
>> >> >          void **value;
>> >> > }key_node;
>> >> >
>> >> > POSIX_Keys_Control is used to manage all keys. And key_node is the
>> >> > structure contains key data and rbtree node.
>> >> I think you might want an rtems_rbtree_control key_tree field in
>> >> POSIX_Keys_Control instead of this key_node* dynamic array.  Then your
>> >> code can add structs containing an rtems_rbtree_node dynamically to
>> >> the key_tree.
>> >
>> > After read the rbtree.h in score, I find I confused the
>> > rtems_rbtree_node
>> > and rtems_rbtree_control. It should be the rtems_rbtree_control here.
>> >
>> >> Also the key_node structure should follow a naming convention of
>> >> POSIX_Keys_Key_node or something similar.
>> >> API_Package_name_Struct_type_name is the general format for
>> >> structures. API_Package_name_Method_name is the general format for
>> >> functions. Note the mixture of lower and upper case letters.
>> >
>> > I see.
>> >
>> >>
>> >> > I'm not quite sure about the Objects_Control member's function in
>> >> > current implementation. I find key = Object.id, in which key is
>> >> > pthread_key_t type, and  _POSIX_Keys_Get(key, &location) is used to
>> >> > find key's corresponding the_key, which is POSIX_Keys_Control type.So
>> >> > is it the only function of Object member ?
>> >> >
>> >> Object_Control means the structure embeds an RTEMS Object so that the
>> >> structure can be managed by the Object Manager whose responsibilities
>> >> include pre-allocating enough objects of a certain type to satisfy
>> >> requests to Create those objects.
>> >>
>> >> It seems to me that the Key (key_node) should be the Object since the
>> >> number of keys is the resource being managed. The present solution
>> >> uses an array of values (one for each thread) because each thread can
>> >> have its own version of a given key. The key is "looked up" by the
>> >> Object Id of the Key and then the requesting thread.  What we should
>> >> prefer is a more scalable solution that does not require
>> >> pre-allocating an array of values for all possible threads.  Something
>> >> like...
>> >> typedef struct {
>> >>           Objects_Control     Object;
>> >>           void     (*destructor)( void * );
>> >>          rtems_rbtree_node Node;
>> >>          Objects_Id thread_id;
>> >>          void **value;
>> >> } POSIX_Keys_Control;
>> >>
>> >> And maybe a global:
>> >> rtems_rbtree_control POSIX_Keys_Tree;
>> >
>> >
>> > I think this is a new and great idea that I haven't thought before,Does
>> > it
>> > mean a single POSIX_Keys_Tree contains all node in the system?
>> yes
>>
>> > I know a rbtree contains only key data belongs to one specific key in my
>> > design above, and I was thinking the idea of manage all keys by a
>> > rbtree,
>> > then there would be a hiearchy: all keys are in one rbtree, and each
>> > key's
>> > data are in their own rbtrees. But I think this design is a little
>> > complex,
>> > and your idea is more uniform. However, will these two differ much in
>> > runtime?
>> >
>> not sure because i do not quite understand your design. but I get the
>> feeling that your design will have a big problem of managing multiple
>> rbtrees simultaneously. I have not tried to do that before. Both
>> approaches seem like they would have similar (log-time) asymptotic
>> behavior.
>>
> I mean all keys are managed in one globle rbtree, in which each node has a
> member of rtems_rbtree_control, like:
> typedef struct {
> Objects_Control Object;
> void (*destructor)(void*);
> rtems_rbtree_node Node;
> rtems_rbtree_control key_tree;
> }POSIX_Keys_Control;
>
> and for each key, all the key data is managed in each key's rbtree, like:
> typedef struct{
> rtems_rbtree_node node;
> Objects_Id thread_id;
> void *value;
> }POSIX_Keys_Key_node;
> However, this design seems more complex. And I don't know what could lead to
> the problem of managing multiple
> rbtrees simultaneously, can you give some example?
>
What do you mean "give some example"?

I agree that the design of multiple rbtree's in a hierarchy is more
complex. It would work, but it seems unnecessary here. A single rbtree
of all the keys should be OK. Lookup/insert/delete times would all be
O(lg n) where n is the total number of keys. In a hierarchical design
the cost is lg k + lg t where k is the number of distinct keys and t
is the number of tasks. The worst-case for the single rbtree is when
every key is used by every thread and n = k*t. Then
lg(n)=lg(k*t)=lg(k)+lg(t) which is the worst-case for the hierarchical
approach. Granted there are cases where the hierarchical approach can
do better, but in worst-case thinking the single rbtree approach is
the best.

Let's take an example. Consider a case where you have 4 distinct keys
and 4 threads. If each key is only used by 1 thread then the
worst-case lookup time for either approach is about lg(4) or 2
branches traversed. Now suppose that 1 of the keys is used by all 4
threads, 1 key is used by 2 threads, and the other 2 are used by 1
thread each. Then the worst-case lookup time for the hierarchical
approach is approx lg(4)+lg(4) = 4 for the key shared by all threads,
and for the single rbtree it is lg(8) = 3. The expected cost for
accessing an unshared key is about lg(4) =2 for hierarchical and
lg(8)=3 for the single rbtree, so as I said sometimes the hierarchical
can do better, but it does so by sacrificing the worst-case
performance.

Also, you should consider how the implementation can be done in the
supercore layer and shared between Posix Keys and Classic Task vars.
Examples of sharing implementations between Posix and Classic APIs are
plentiful. See for example the corebarrier in score and corresponding
barrier interfaces in posix/classic.

-Gedare

> -zw_yao
>>
>> >>
>> >> Then you would implement an rbtree_compare function that will combine
>> >> the POSIX_Keys_control.Object.id with POSIX_Keys_control.thread_id as
>> >> a "key" for the rbtree to use for storing each POSIX_Keys_Control.
>> >>
>> > I see, I can compare POSIX_Keys_control.Object.id first and if they are
>> > equal, then compare the POSIX_Keys_control.thread_id.
>> >
>> >
>> >> all key related operations are described as follow:
>> >> - key create:
>> >> create POSIX_Keys_Control instance and intialize an empty rbtree, in
>> >> which rtems_rbtree_control instance will be created and an rbtree
>> >> node's key compare function is also needed. Thread_id is compared in
>> >> the compare function. So this approach doesdn't consider allocate same
>> >> data for the same thread in the same key, because only different
>> >> Thread_id are comparable. But I find something about duplicate node in
>> >> the Gedare's rbtree patch, maybe the duplicate feature also can be
>> >> added into POSIX key.
>> >>
>> >>
>> >> You still want unique rbtree comparisons so that a thread can
>> >> distinguish its own keys, unless it is valid for a thread to allocate
>> >> multiple values with the same key?
>> >>
>> >> Key create should not create the red-black tree; the rbtree should be
>> >> created during initialization of the POSIX_Keys manager---which by the
>> >> way is improperly named right now as POSIX_Key_Manager_initialization
>> >> and should be renamed POSIX_Keys_Manager_initialization with an s on
>> >> Keys (or just POSIX_Keys_Initialization).
>> >>
>> > I didn't notice the  POSIX_Key_Manager_initialization before, thanks.
>> > BTW
>> > I've a question about the _Objects_Initialize_information(), which
>> > _POSIX_Key_Manager_initialization calls. I read the code of
>> > _Objects_Initialize_information(), but still don't know what the maximum
>> > parameter is used for? I think it's not for determining the memory size
>> > of
>> > all objects in one manager and then allocating such size of memory, is
>> > it?
>> >
>> maximum determines the total number of that kind of object. it is
>> controlled by some CONFIGURE_MAXIMUM_XXX, e.g.
>> CONIFIGURE_MAXIMUM_POSIX_KEYS.
>>
>> -Gedare
>>
>> >> > - key delete
>> >> > delete all the nodes in rbtree by rtems_rbtree_get_min() or
>> >> > rtems_rbtree_get_max(), and delete the RBTree_Control,
>> >> > POSIX_Keys_Control instance. The key data's deallocation is done by
>> >> > user.
>> >> >
>> >> > - key get specific
>> >> > we can use _RBTree_Find() to do the actually work behind
>> >> > get_specific(),  the runtime is O(log(n))
>> >> >
>> >> > - key set specific
>> >> > after a proper key_node is create, we can use _RBTree_Insert() to do
>> >> > the set specific. the runtime is rbtree insert runtime, which is
>> >> > O(log(n)).
>> >> >
>> >> > I'm not sure whether this design is appropriate and this design is
>> >> > very simple, need many more work to do. Hope further discussion to
>> >> > make it more clear!
>> >> >
>> >> Simple is good. I think you're on the right track other than my few
>> >> comments about organizing the structures. You have the right ideas for
>> >> how to implement the Keys functions I believe.
>> >> -Gedare
>> >
>> > Yeah, it remind me the K.I.S.S. principle!
>> >
>> > -best regards!
>> > -zw_yao
>> >>
>> >>
>> >> > --best regards!
>> >> > --zw_yao
>> >> > _______________________________________________
>> >> > rtems-devel mailing list
>> >> > rtems-devel at rtems.org
>> >> > http://www.rtems.org/mailman/listinfo/rtems-devel
>> >
>> >
>
>

More information about the devel mailing list