<br><br><div class="gmail_quote">2012/5/8 Gedare Bloom <span dir="ltr"><<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5">On Tue, May 8, 2012 at 3:17 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
><br>
><br>
> 2012/5/7 Gedare Bloom <<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>><br>
>><br>
>> On Mon, May 7, 2012 at 11:16 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
>> > I'm terribly sorry for my late reply. I'm off for my weekend.<br>
>> ><br>
>> Most of us are. :)<br>
>><br>
>> > 2012/5/4 Gedare Bloom <<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>><br>
>> >><br>
>> >> On Fri, May 4, 2012 at 3:28 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
>> >> > Hi, all. I'm working on the "Use hash or map in POSIX keys" project.<br>
>> >> > As Joel said, the first thing to be determined is the problem of what<br>
>> >> > data goes with each thread and what goes with each key. I find it's<br>
>> >> > difficult to design the interface without some specific approach. And<br>
>> >> > since the rbtree api is available in RTEMS, I have tried to do the<br>
>> >> > design in the rbtree approach.<br>
>> >> ><br>
>> >> Good. The rbtree should support an efficient map operation.<br>
>> >><br>
>> > Gedare, thanks for your reply!<br>
>> ><br>
>> >><br>
>> >> > I find 2 data structures need revised(added): POSIX_Keys_Control and<br>
>> >> > key_node.<br>
>> >> ><br>
>> >> > typedef struct {<br>
>> >> > Objects_Control Object;<br>
>> >> > void (*destructor)( void * );<br>
>> >> > key_node * key_node_ptr;<br>
>> >> > }POSIX_Keys_Control;<br>
>> >> ><br>
>> >> > typedef struct{<br>
>> >> > rtems_rbtree_node Node;<br>
>> >> > Objects_Id thread_id;<br>
>> >> > void **value;<br>
>> >> > }key_node;<br>
>> >> ><br>
>> >> > POSIX_Keys_Control is used to manage all keys. And key_node is the<br>
>> >> > structure contains key data and rbtree node.<br>
>> >> I think you might want an rtems_rbtree_control key_tree field in<br>
>> >> POSIX_Keys_Control instead of this key_node* dynamic array. Then your<br>
>> >> code can add structs containing an rtems_rbtree_node dynamically to<br>
>> >> the key_tree.<br>
>> ><br>
>> > After read the rbtree.h in score, I find I confused the<br>
>> > rtems_rbtree_node<br>
>> > and rtems_rbtree_control. It should be the rtems_rbtree_control here.<br>
>> ><br>
>> >> Also the key_node structure should follow a naming convention of<br>
>> >> POSIX_Keys_Key_node or something similar.<br>
>> >> API_Package_name_Struct_type_name is the general format for<br>
>> >> structures. API_Package_name_Method_name is the general format for<br>
>> >> functions. Note the mixture of lower and upper case letters.<br>
>> ><br>
>> > I see.<br>
>> ><br>
>> >><br>
>> >> > I'm not quite sure about the Objects_Control member's function in<br>
>> >> > current implementation. I find key = Object.id, in which key is<br>
>> >> > pthread_key_t type, and _POSIX_Keys_Get(key, &location) is used to<br>
>> >> > find key's corresponding the_key, which is POSIX_Keys_Control type.So<br>
>> >> > is it the only function of Object member ?<br>
>> >> ><br>
>> >> Object_Control means the structure embeds an RTEMS Object so that the<br>
>> >> structure can be managed by the Object Manager whose responsibilities<br>
>> >> include pre-allocating enough objects of a certain type to satisfy<br>
>> >> requests to Create those objects.<br>
>> >><br>
>> >> It seems to me that the Key (key_node) should be the Object since the<br>
>> >> number of keys is the resource being managed. The present solution<br>
>> >> uses an array of values (one for each thread) because each thread can<br>
>> >> have its own version of a given key. The key is "looked up" by the<br>
>> >> Object Id of the Key and then the requesting thread. What we should<br>
>> >> prefer is a more scalable solution that does not require<br>
>> >> pre-allocating an array of values for all possible threads. Something<br>
>> >> like...<br>
>> >> typedef struct {<br>
>> >> Objects_Control Object;<br>
>> >> void (*destructor)( void * );<br>
>> >> rtems_rbtree_node Node;<br>
>> >> Objects_Id thread_id;<br>
>> >> void **value;<br>
>> >> } POSIX_Keys_Control;<br>
>> >><br>
>> >> And maybe a global:<br>
>> >> rtems_rbtree_control POSIX_Keys_Tree;<br>
>> ><br>
>> ><br>
>> > I think this is a new and great idea that I haven't thought before,Does<br>
>> > it<br>
>> > mean a single POSIX_Keys_Tree contains all node in the system?<br>
>> yes<br>
>><br>
>> > I know a rbtree contains only key data belongs to one specific key in my<br>
>> > design above, and I was thinking the idea of manage all keys by a<br>
>> > rbtree,<br>
>> > then there would be a hiearchy: all keys are in one rbtree, and each<br>
>> > key's<br>
>> > data are in their own rbtrees. But I think this design is a little<br>
>> > complex,<br>
>> > and your idea is more uniform. However, will these two differ much in<br>
>> > runtime?<br>
>> ><br>
>> not sure because i do not quite understand your design. but I get the<br>
>> feeling that your design will have a big problem of managing multiple<br>
>> rbtrees simultaneously. I have not tried to do that before. Both<br>
>> approaches seem like they would have similar (log-time) asymptotic<br>
>> behavior.<br>
>><br>
> I mean all keys are managed in one globle rbtree, in which each node has a<br>
> member of rtems_rbtree_control, like:<br>
> typedef struct {<br>
> Objects_Control Object;<br>
> void (*destructor)(void*);<br>
> rtems_rbtree_node Node;<br>
> rtems_rbtree_control key_tree;<br>
> }POSIX_Keys_Control;<br>
><br>
> and for each key, all the key data is managed in each key's rbtree, like:<br>
> typedef struct{<br>
> rtems_rbtree_node node;<br>
> Objects_Id thread_id;<br>
> void *value;<br>
> }POSIX_Keys_Key_node;<br>
> However, this design seems more complex. And I don't know what could lead to<br>
> the problem of managing multiple<br>
> rbtrees simultaneously, can you give some example?<br>
><br>
</div></div>What do you mean "give some example"?<br></blockquote><div>I mean the example of the problem of managing multiple rbtrees simultaneously. <br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
I agree that the design of multiple rbtree's in a hierarchy is more<br>
complex. It would work, but it seems unnecessary here. A single rbtree<br>
of all the keys should be OK. Lookup/insert/delete times would all be<br>
O(lg n) where n is the total number of keys. In a hierarchical design<br>
the cost is lg k + lg t where k is the number of distinct keys and t<br>
is the number of tasks. The worst-case for the single rbtree is when<br>
every key is used by every thread and n = k*t. Then<br>
lg(n)=lg(k*t)=lg(k)+lg(t) which is the worst-case for the hierarchical<br>
approach. Granted there are cases where the hierarchical approach can<br>
do better, but in worst-case thinking the single rbtree approach is<br>
the best.<br>
<br>
Let's take an example. Consider a case where you have 4 distinct keys<br>
and 4 threads. If each key is only used by 1 thread then the<br>
worst-case lookup time for either approach is about lg(4) or 2<br>
branches traversed. Now suppose that 1 of the keys is used by all 4<br>
threads, 1 key is used by 2 threads, and the other 2 are used by 1<br>
thread each. Then the worst-case lookup time for the hierarchical<br>
approach is approx lg(4)+lg(4) = 4 for the key shared by all threads,<br>
and for the single rbtree it is lg(8) = 3. The expected cost for<br>
accessing an unshared key is about lg(4) =2 for hierarchical and<br>
lg(8)=3 for the single rbtree, so as I said sometimes the hierarchical<br>
can do better, but it does so by sacrificing the worst-case<br>
performance.<br></blockquote><div>Very helpful, Thanks! <br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Also, you should consider how the implementation can be done in the<br>
supercore layer and shared between Posix Keys and Classic Task vars.<br>
Examples of sharing implementations between Posix and Classic APIs are<br>
plentiful. See for example the corebarrier in score and corresponding<br>
barrier interfaces in posix/classic.<br>
<span class="HOEnZb"><font color="#888888"><br></font></span></blockquote><div>OK, I think I'm not familiar with Task variable enough, I'll also read the cpukit/rtems/src/taskvariable*.c carefully.<br> <br>>It occurred to me that you might also be able to put the<br>
>_RBTree_Control in the thread control block (tcb) of each thread. then<br>
>you can store the keys per thread and lookup time will be log in the<br>
>number of keys a particular thread uses.<br><br><div class="yj6qo ajU"><div id=":10x" class="ajR" tabindex="0">Will it be added to the tcb's <img class="ajT" src="images/cleardot.gif">API_Extensions member or others? I'll take a look at some examples about tcb to get familiar with it.<br>
<br>-zw_yao<br></div></div><br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="HOEnZb"><font color="#888888">
-Gedare<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
> -zw_yao<br>
>><br>
>> >><br>
>> >> Then you would implement an rbtree_compare function that will combine<br>
>> >> the <a href="http://POSIX_Keys_control.Object.id" target="_blank">POSIX_Keys_control.Object.id</a> with POSIX_Keys_control.thread_id as<br>
>> >> a "key" for the rbtree to use for storing each POSIX_Keys_Control.<br>
>> >><br>
>> > I see, I can compare <a href="http://POSIX_Keys_control.Object.id" target="_blank">POSIX_Keys_control.Object.id</a> first and if they are<br>
>> > equal, then compare the POSIX_Keys_control.thread_id.<br>
>> ><br>
>> ><br>
>> >> all key related operations are described as follow:<br>
>> >> - key create:<br>
>> >> create POSIX_Keys_Control instance and intialize an empty rbtree, in<br>
>> >> which rtems_rbtree_control instance will be created and an rbtree<br>
>> >> node's key compare function is also needed. Thread_id is compared in<br>
>> >> the compare function. So this approach doesdn't consider allocate same<br>
>> >> data for the same thread in the same key, because only different<br>
>> >> Thread_id are comparable. But I find something about duplicate node in<br>
>> >> the Gedare's rbtree patch, maybe the duplicate feature also can be<br>
>> >> added into POSIX key.<br>
>> >><br>
>> >><br>
>> >> You still want unique rbtree comparisons so that a thread can<br>
>> >> distinguish its own keys, unless it is valid for a thread to allocate<br>
>> >> multiple values with the same key?<br>
>> >><br>
>> >> Key create should not create the red-black tree; the rbtree should be<br>
>> >> created during initialization of the POSIX_Keys manager---which by the<br>
>> >> way is improperly named right now as POSIX_Key_Manager_initialization<br>
>> >> and should be renamed POSIX_Keys_Manager_initialization with an s on<br>
>> >> Keys (or just POSIX_Keys_Initialization).<br>
>> >><br>
>> > I didn't notice the POSIX_Key_Manager_initialization before, thanks.<br>
>> > BTW<br>
>> > I've a question about the _Objects_Initialize_information(), which<br>
>> > _POSIX_Key_Manager_initialization calls. I read the code of<br>
>> > _Objects_Initialize_information(), but still don't know what the maximum<br>
>> > parameter is used for? I think it's not for determining the memory size<br>
>> > of<br>
>> > all objects in one manager and then allocating such size of memory, is<br>
>> > it?<br>
>> ><br>
>> maximum determines the total number of that kind of object. it is<br>
>> controlled by some CONFIGURE_MAXIMUM_XXX, e.g.<br>
>> CONIFIGURE_MAXIMUM_POSIX_KEYS.<br>
>><br>
>> -Gedare<br>
>><br>
>> >> > - key delete<br>
>> >> > delete all the nodes in rbtree by rtems_rbtree_get_min() or<br>
>> >> > rtems_rbtree_get_max(), and delete the RBTree_Control,<br>
>> >> > POSIX_Keys_Control instance. The key data's deallocation is done by<br>
>> >> > user.<br>
>> >> ><br>
>> >> > - key get specific<br>
>> >> > we can use _RBTree_Find() to do the actually work behind<br>
>> >> > get_specific(), the runtime is O(log(n))<br>
>> >> ><br>
>> >> > - key set specific<br>
>> >> > after a proper key_node is create, we can use _RBTree_Insert() to do<br>
>> >> > the set specific. the runtime is rbtree insert runtime, which is<br>
>> >> > O(log(n)).<br>
>> >> ><br>
>> >> > I'm not sure whether this design is appropriate and this design is<br>
>> >> > very simple, need many more work to do. Hope further discussion to<br>
>> >> > make it more clear!<br>
>> >> ><br>
>> >> Simple is good. I think you're on the right track other than my few<br>
>> >> comments about organizing the structures. You have the right ideas for<br>
>> >> how to implement the Keys functions I believe.<br>
>> >> -Gedare<br>
>> ><br>
>> > Yeah, it remind me the K.I.S.S. principle!<br>
>> ><br>
>> > -best regards!<br>
>> > -zw_yao<br>
>> >><br>
>> >><br>
>> >> > --best regards!<br>
>> >> > --zw_yao<br>
>> >> > _______________________________________________<br>
>> >> > rtems-devel mailing list<br>
>> >> > <a href="mailto:rtems-devel@rtems.org">rtems-devel@rtems.org</a><br>
>> >> > <a href="http://www.rtems.org/mailman/listinfo/rtems-devel" target="_blank">http://www.rtems.org/mailman/listinfo/rtems-devel</a><br>
>> ><br>
>> ><br>
><br>
><br>
</div></div></blockquote></div><br>