<br><br><div class="gmail_quote">2012/6/18 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 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 Key<br>
>> > project. There are several reasons that I start to code without deciding<br>
>> > which approach is best(there are several approaches have been 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 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 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 Key<br>
>> > data<br>
>> > only by Object manager(also described in [0]) is really immature. 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 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 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 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 object<br>
> number, because the number of key's value can be very large, but not 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 to<br>
>> > one_rbtree branch in github repo[1]) , and the 5th thread delete 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 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 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 all<br>
>> > the<br>
>> > key nodes from the rbtree in that key by traverse the list. I wonder 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 Key<br>
> delete<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>
</div></div>OK that does seem to say all keys should be removed having the same<br>
pthread_key_t.<br>
<div class="im"><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? If<br>
> so, we needn't the list to keep track.<br>
</div>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></blockquote><div>Great, 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>
>><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 refer<br>
>> > some<br>
>> > code in other POSIX manager, all of them used _Workspace_Allocate and 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 create<br>
> and key setspecific which write something need protection, right? Is<br>
> dispatch disable lock enable to do the protection?<br>
><br>
</div></div>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>
<div class="HOEnZb"><div class="h5"><br></div></div></blockquote><div>Very instructive to me:) <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>
>> 4. Key delete<br>
>> work in key delete:<br>
>> - deallocate all nodes of specific key by iterate the key node list, 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 necessary<br>
>> > information about key to the thread's API_Extensions area. Actually, I<br>
>> > add a<br>
>> > list head pointer to the POSIX_API_Control structure, the pointer 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 this<br>
>> > list<br>
>> > and then delete the whole list. And we need add node to this list 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></div></div></blockquote><div> </div><div>I've implemented this thread delete part now. However, still not sure about whether we need delete the key nodes of deleted thread from rbtree when thread deleted. I think this would matter a lot: if we needed delete the key nodes of deleted thread from rbtree when thread deleted, then the list(or other data structure) in key control structure must keep <span class="st">synchronous with the list in the thread extension. then both deletion operation (key deletion and thread deletion) would take much more time. So I think I need make clear about this.<br>
<br>there also are some problems in my first implementation:<br>- when I run the psxtest01.exe test in the testsuites, I get:<br></span>no workspace available FAILED -- expected (resources still outstanding) got (successful completion)<br>
I know the reason is that there is no workspace allocation in this implementation when key create. I think the psxtest01 test need also be revised.<br>- in the psxtest03.exe test, I get:<br><br><div style="margin-left:40px">
*** 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: 100 destructor_ran == false<br></div><br>while the original output is:<br><div style="margin-left:40px">*** 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></div>I run sparc-rtems4.11-gdb on it, find the problem is that the destructor function in psxtest03 hasn't been properly run. And when I step into _POSIX_Keys_Run_destructors() function, however I can't get any further info about my code. Because when I try to print variable in the _POSIX_Keys_Run_destructors() function, most of them are "optimized out". And I also changed the CFLAGS(remove -O2) in psxtest03 Makefile, but still doesn't help. How can I solve this problem? <br>
<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">
>> ><span class="st"></span><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 more.<br>
>><br>
>><br>
>> ><br>
>> > thanks for any reply on this!<br>
>> ><br>
>> > links:<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>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Best wishes!<br>Zhongwei Yao<br><br>