<br><br><div class="gmail_quote">2012/6/20 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, Jun 19, 2012 at 4:59 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
><br>
><br>
> 2012/6/18 Gedare Bloom <<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>><br>
>><br>
>> On Sun, Jun 17, 2012 at 11:36 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
>> ><br>
>> ><br>
>> > 2012/6/15 Gedare Bloom <<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>><br>
>> >><br>
>> >> On Fri, Jun 15, 2012 at 6:02 AM, Ashi <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
>> >> > Hi, all.<br>
>> >> > Last two weeks, I'm working on the one-rbtree approach in the POSIX<br>
>> >> > Key<br>
>> >> > project. There are several reasons that I start to code without<br>
>> >> > deciding<br>
>> >> > which approach is best(there are several approaches have been<br>
>> >> > discussed<br>
>> >> > before, here[0] is the summary I have done before): first, I want to<br>
>> >> > make<br>
>> >> > myself more clear about the problem lies behind the POSIX Key by<br>
>> >> > coding<br>
>> >> > first. Second, we may also need to implement several different<br>
>> >> > approaches<br>
>> >> > and evaluate them finally. This post is a partly summary of<br>
>> >> > one-rbtree<br>
>> >> > approach and also with many problems in it. By the way, after try to<br>
>> >> > implement the one-rbtree approach, I find the approach manage POSIX<br>
>> >> > Key<br>
>> >> > data<br>
>> >> > only by Object manager(also described in [0]) is really immature.<br>
>> >> > I've<br>
>> >> > tried<br>
>> >> > to implemented that before starting the one-rbtree approach, however,<br>
>> >> > I'm<br>
>> >> > stuck and turn to one-rbtree approach.<br>
>> >> ><br>
>> >> Can you expand on why the object manager approach does not work?<br>
>> ><br>
>> > Yeah, I should explain it earlier:<br>
>> > When I came to the Key getspecific stage of this approach, I found using<br>
>> > object manager to manage all key's value didn't  simplify the key<br>
>> > getspecific at all. The key getspecific interface is:<br>
>> > void *pthread_getspecific( pthread_key_t  key )<br>
>> > what we want to do is return the key's data by using the input key and<br>
>> > the<br>
>> > implicit imput the executing thread id. Now if we used object manager to<br>
>> > manage all key's value, that is allocating one object such as:<br>
>> > typedef struct {<br>
>> > Object object;<br>
>> > void *value;<br>
>> > }<br>
>> > then the work becomes finding a kind of mapping between input<br>
>> > parameter(the<br>
>> > key and executing thread id) and <a href="http://object.id" target="_blank">object.id</a>. That can be done like the<br>
>> > one-rbtree approah or something other. After get the <a href="http://object.id" target="_blank">object.id</a>, we can<br>
>> > get<br>
>> > the value pointer by the object manager, work is done. This kind design<br>
>> > didn't simplify anything compared with one-rbtree approach, so I give up<br>
>> > this design. I have thought about other reason like the limitation of<br>
>> > object<br>
>> > number, because the number of key's value can be very large, but not<br>
>> > clear<br>
>> > whether that's a limitation.<br>
>> >><br>
>> >> ><br>
>> >> > There are 6 scenarios which we need deal with in POSIX key:<br>
>> >> > 0. Key manage initialization<br>
>> >> > 1. Key create<br>
>> >> > 2. Key setspecific<br>
>> >> > 3. Key getspecific<br>
>> >> > 4. Key delete<br>
>> >> > 5. Thread delete<br>
>> >> ><br>
>> >> > In the one-rbtree approach, I've done the 0~4(I've committed the code<br>
>> >> > to<br>
>> >> > one_rbtree branch in github repo[1]) , and the 5th thread delete<br>
>> >> > hasn't<br>
>> >> > been<br>
>> >> > done, and needs more discussion(I'll list the problem below):<br>
>> >> > 0. Key manage initialization<br>
>> >> > I added two data structures in key.h, the POSIX_Keys_Rbtree_node is<br>
>> >> > the<br>
>> >> > node<br>
>> >> > of the rbtree which holds all keys' values, and use Key and Thread_id<br>
>> >> > member<br>
>> >> > as rbtree key. POSIX_Keys_List_node is the node of a list which is<br>
>> >> > used<br>
>> >> > to<br>
>> >> > save all nodes in one key or all nodes in one thread.<br>
>> >> ><br>
>> >> > typedef struct {<br>
>> >> >   /** This field is the rbtree node structure. */<br>
>> >> >   RBTree_Node Node;<br>
>> >> Structure field names are usually lower-case, so "node".<br>
>> ><br>
>> > OK.<br>
>> >><br>
>> >><br>
>> >> >   /** This field is the POSIX key used as an rbtree key */<br>
>> >> >   pthread_key_t Key;<br>
>> >> >   /** This field is the Thread id also used as an rbtree key */<br>
>> >> >   Objects_Id Thread_id;<br>
>> >> >   /** This field points to the POSIX key value of specific thread */<br>
>> >> >   void *Value;<br>
>> >> >  }  POSIX_Keys_Rbtree_node;<br>
>> >> ><br>
>> >> > typedef struct POSIX_Keys_List_node_ {<br>
>> >> >   /** This field is the pointer which points to the next node in the<br>
>> >> > list */<br>
>> >> >   struct POSIX_Keys_List_node_ *Next;<br>
>> >> >   /** This field is the key of list node */<br>
>> >> >   POSIX_Keys_Rbtree_node *Rbnode;<br>
>> >> >  }  POSIX_Keys_List_node;<br>
>> >> ><br>
>> >> Instead of writing your own linked list you should use RTEMS Chains<br>
>> >> (if you need a linked list).<br>
>> ><br>
>> > I'll check that.<br>
>> >><br>
>> >><br>
>> >> > and revises the POSIX_Keys_Control structure, it has a member Head,<br>
>> >> > which<br>
>> >> > points to the list of all node in specific key. The reason I attach a<br>
>> >> > list<br>
>> >> > of nodes in one key is that when key deletion happens, I can delete<br>
>> >> > all<br>
>> >> > the<br>
>> >> > key nodes from the rbtree in that key by traverse the list. I wonder<br>
>> >> > is<br>
>> >> > there any better way to get all nodes belong one key from the rbtree?<br>
>> >> ><br>
>> >> Does key delete remove all the keys having the same pthread_key_t, or<br>
>> >> only those keys belonging to the executing thread? If only the one key<br>
>> >> needs to be removed then I don't see the need for this list at all,<br>
>> >> you would just "extract" the one key.<br>
>> ><br>
>> > I think key delete will remove all the key's value having the same<br>
>> > pthread_key_t, so we need track one key's all value. Here is the POSIX<br>
>> > Key<br>
>> > delete<br>
>> ><br>
>> > standard(<a href="http://pubs.opengroup.org/onlinepubs/009604499/functions/pthread_key_delete.html" target="_blank">http://pubs.opengroup.org/onlinepubs/009604499/functions/pthread_key_delete.html</a>).<br>

>> OK that does seem to say all keys should be removed having the same<br>
>> pthread_key_t.<br>
>><br>
>> > I wonder if we can search the rbtree(here every node has two keys:<br>
>> > pthread_key_t key and Object_Id thread_id) only specify one key of two?<br>
>> > If<br>
>> > so, we needn't the list to keep track.<br>
>> If you use pthread_key_t as a primary key and thread_id as a secondary<br>
>> key for sorting, then you might be able to use rbtree_successor<br>
>> function to iterate through the keys having identical pthread_key_t<br>
>> and increasing values of thread_id.<br>
><br>
> Great, I'll try it.<br>
>><br>
>><br>
>> >><br>
>> >><br>
>> >> > typedef struct {<br>
>> >> >    /** This field is the Object control structure. */<br>
>> >> >    Objects_Control     Object;<br>
>> >> >    /** This field is the data destructor. */<br>
>> >> >    void (*destructor) (void *);<br>
>> >> >    /** This field is the head of key's node list */<br>
>> >> >    POSIX_Keys_List_node *Head;<br>
>> >> >  }  POSIX_Keys_Control;<br>
>> >> ><br>
>> >> > The work during the POSIX Key manager initialization is:<br>
>> >> > - besides the _Objects_Initialize_information, the global rbtree<br>
>> >> > _POSIX_Keys_Rbtree is initialized to an empty rbtree.<br>
>> >> ><br>
>> >> > 1. Key create<br>
>> >> > work in key create:<br>
>> >> > - allocate the POSIX_Keys_Control object and initialize it.<br>
>> >> ><br>
>> >> > 2. Key setspecific<br>
>> >> > work in key setspecific:<br>
>> >> > - allocate a POSIX_Keys_Rbtree_node object and a POSIX_Keys_List_node<br>
>> >> > object<br>
>> >> > from RTEMS workspace<br>
>> >> > - add the rbtree node to the rbtree<br>
>> >> > - add the list node to the key's list<br>
>> >> > problem:<br>
>> >> > I'm not really clear about the workspace and heap memory, I just<br>
>> >> > refer<br>
>> >> > some<br>
>> >> > code in other POSIX manager, all of them used _Workspace_Allocate and<br>
>> >> > no<br>
>> >> > malloc there. Could anyone explain the difference between them? Or is<br>
>> >> > there<br>
>> >> > any doc about that?<br>
>> >> ><br>
>> >> Workspace is for allocation of kernel objects. Not sure if there is an<br>
>> >> explanation somewhere, although probably there ought to be...<br>
>> >> Workspace is basically like heap (malloc), except that the workspace<br>
>> >> is constrained in size based on application configuration. These<br>
>> >> objects are rightly allocated from the workspace.<br>
>> ><br>
>> ><br>
>> >><br>
>> >> > 3. Key getspecific<br>
>> >> > work in key getspecific:<br>
>> >> > - get the node in the rbtree<br>
>> >> > problem:<br>
>> >> > - I find a _Thread_Enable_dispatch() function in the current<br>
>> >> > keygetspecfic.c<br>
>> >> > file, and don't know what is it used for.<br>
>> >> ><br>
>> >> _POSIX_Keys_Get implicitly obtains a dispatch disable lock (via<br>
>> >> Objects_Get). This is releasing the lock. If your code does not use<br>
>> >> Objects_Get then probably it does not need to enable dispatching...<br>
>> >> although you are likely having to protect the global rbtree somehow<br>
>> >> with a critical section?<br>
>> ><br>
>> > I haven't consided any about the critical section before, I think key<br>
>> > create<br>
>> > and key setspecific which write something need protection, right? Is<br>
>> > dispatch disable lock enable to do the protection?<br>
>> ><br>
>> I think you want ISR_Disable/Enable. Note that reading without a lock<br>
>> would be a problem if another thread can acquire the lock and write,<br>
>> so you need to protect any shared memory / data structure for both<br>
>> reading and writing from concurrent access.<br>
>><br>
> Very instructive to me:)<br>
>><br>
>> ><br>
>> >> 4. Key delete<br>
>> >> work in key delete:<br>
>> >> - deallocate all nodes of specific key by iterate the key node list,<br>
>> >> and<br>
>> >> then delete it from rbtree, also delete it from the list<br>
>> >> - deallocate the POSIX_Key_Control object<br>
>> >><br>
>> >><br>
>> >> Again unclear to me if the key delete should apply to all keys with<br>
>> >> the same pthread_key_t or only the one for a particular thread. We<br>
>> >> need to get an answer to this question before any decision can be made<br>
>> >> about the best path forward.<br>
>> >><br>
>> >> > 5. Thread delete<br>
>> >> > I find when a posix thread deleted, a _POSIX_Keys_Run_destructors()<br>
>> >> > function<br>
>> >> > runs, then all key's data in the deleted thread is destructed. I have<br>
>> >> > some<br>
>> >> > idea about it, but haven't implement it. I'm thinking add the<br>
>> >> > necessary<br>
>> >> > information about key to the thread's API_Extensions area. Actually,<br>
>> >> > I<br>
>> >> > add a<br>
>> >> > list head pointer to the POSIX_API_Control structure, the pointer<br>
>> >> > points<br>
>> >> > to<br>
>> >> > a list of nodes which contains all the key's value pointer in one<br>
>> >> > thread.<br>
>> >> > When thread exits, we can deallocate all the key data by traverse<br>
>> >> > this<br>
>> >> > list<br>
>> >> > and then delete the whole list. And we need add node to this list<br>
>> >> > when<br>
>> >> > key<br>
>> >> > setspecific. When Key deletes nothing should be done on this list. I<br>
>> >> > think<br>
>> >> > we needn't delete key nodes of deleted thread from rbtree when thread<br>
>> >> > deleted, and the only work should be done when thread deleted is<br>
>> >> > deallocating the key's data in that thread, right?<br>
><br>
><br>
> I've implemented this thread delete part now. However, still not sure about<br>
> whether we need delete the key nodes of deleted thread from rbtree when<br>
> thread deleted. I think this would matter a lot: if we needed  delete the<br>
> key nodes of deleted thread from rbtree when thread deleted, then the<br>
> list(or other data structure) in key control structure must keep synchronous<br>
> with the list in the thread extension. then both deletion operation (key<br>
> deletion and thread deletion) would take much more time. So I think I need<br>
> make clear about this.<br>
><br>
</div></div>This is tricky but I think necessary. You might be able to put a chain<br>
link in the key node to enqueue key node from the TCB while<br>
simultaneously maintaining an rbtree node for the key node to handle<br>
searching by pthread_key_t. So inserting a new key would require<br>
inserting to the rbtree, and inserting to the TCB->keys_chain... When<br>
deleting a key you would search the key in the rbtree, store pointer<br>
next to rbtree_next, extract key node from the TCB->keys_chain,<br>
extract key node from the rbtree, and continue while next->key ==<br>
pthread_key_t... When deleting a thread you would iterate through the<br>
TCB->keys_chain extracting from rbtree and chain.<br></blockquote><div>Good idea, I'll try it. <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">

<div><div class="h5"><br>
> there also are some problems in my first implementation:<br>
> - when I run the psxtest01.exe test in the testsuites, I get:<br>
> no workspace available FAILED -- expected (resources still outstanding) got<br>
> (successful completion)<br>
> I know the reason is that there is no workspace allocation in this<br>
> implementation when key create. I think the psxtest01 test need also be<br>
> revised.<br>
> - in the psxtest03.exe test, I get:<br>
><br>
> *** TEST KEY 03 ***<br>
> Init - pthread_key_create with NULL destructor - OK<br>
> Init - pthread_create - OK<br>
> Init - sleep - let thread run - OK<br>
> Test_Thread - pthread_setspecific - OK<br>
> Test_Thread - pthread_exit to run key destructors - OK<br>
> Init - pthread_key_delete - OK<br>
> Init - pthread_key_create with non-NULL destructor - OK<br>
> Init - pthread_create - OK<br>
> Init - sleep - let thread run - OK<br>
> Test_Thread - pthread_setspecific - OK<br>
> Test_Thread - pthread_exit to run key destructors - OK<br>
> Init - verify destructor did NOT ran<br>
> ../../../../../../../rtems/c/src/../../testsuites/psxtests/psxkey03/init.c:<br>
> 100 destructor_ran == false<br>
><br>
> while the original output is:<br>
> *** TEST KEY 03 ***<br>
> Init - pthread_key_create with NULL destructor - OK<br>
> Init - pthread_create - OK<br>
> Init - sleep - let thread run - OK<br>
> Test_Thread - pthread_setspecific - OK<br>
> Test_Thread - pthread_exit to run key destructors - OK<br>
> Init - pthread_key_delete - OK<br>
> Init - pthread_key_create with non-NULL destructor - OK<br>
> Init - pthread_create - OK<br>
> Init - sleep - let thread run - OK<br>
> Test_Thread - pthread_setspecific - OK<br>
> Test_Thread - pthread_exit to run key destructors - OK<br>
> Init - verify destructor did NOT ran<br>
> Init - pthread_key_delete - OK<br>
> *** END OF TEST KEY 03 ***<br>
> I run sparc-rtems4.11-gdb on it, find the problem is that the destructor<br>
> function in psxtest03 hasn't been properly run. And when I step into<br>
> _POSIX_Keys_Run_destructors() function, however I can't get any further info<br>
> about my code. Because when I try to print variable in the<br>
> _POSIX_Keys_Run_destructors() function, most of them are "optimized out".<br>
> And I also changed the CFLAGS(remove -O2) in psxtest03 Makefile, but still<br>
> doesn't help. How can I solve this problem?<br>
><br>
</div></div>You could try to remove optimize flags from the<br>
c/src/lib/libbsp/sparc/erc32/make/custom/erc32 --- these flags control<br>
the optimization level for the rtems build.<br>
<div class="HOEnZb"><div class="h5"><br></div></div></blockquote><div>Great, I've tried. Now, the one-tree version can pass those tree tests. <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div class="HOEnZb"><div class="h5">
>> >> ><br>
>> >> I think a chain pointing to all of a thread's keys could work fine...<br>
>> >> although this thread-deletion requirement makes me think that every<br>
>> >> thread could just have an rbtree of its own keys. The overhead of an<br>
>> >> rbtree versus a chain is not a lot, and this approach would save<br>
>> >> having a separate list for each thread's keys. You would just use a<br>
>> >> thread's "local" keys rbtree. I'm not sure you would even need locking<br>
>> >> in this case... interesting.<br>
>> ><br>
>> > Yeah, I'm also thinking about one rbtree per thread design. I'll dig<br>
>> > more.<br>
>> >><br>
>> >><br>
>> >> ><br>
>> >> > thanks for any reply on this!<br>
>> >> ><br>
>> >> > links:<br>
>> >> ><br>
>> >> ><br>
>> >> > [0]<a href="https://docs.google.com/document/d/1orDfUJdnxbxizClFNcOVbh0t3T0vtmt5FYJETSNb6KE/edit" target="_blank">https://docs.google.com/document/d/1orDfUJdnxbxizClFNcOVbh0t3T0vtmt5FYJETSNb6KE/edit</a><br>

>> >> > [1]<a href="https://github.com/ashi08104/rtems/tree/one_rbtree#" target="_blank">https://github.com/ashi08104/rtems/tree/one_rbtree#</a><br>
>> >> > --<br>
>> >> > Best wishes!<br>
>> >> > Zhongwei Yao<br>
>> >> ><br>
>> >> ><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>
>> ><br>
>> > --<br>
>> > Best wishes!<br>
>> > Zhongwei Yao<br>
>> ><br>
><br>
><br>
><br>
><br>
> --<br>
> Best wishes!<br>
> Zhongwei Yao<br>
><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Best wishes!<br>Zhongwei Yao<br><br>