[GSoC2012]the problem of one-rbtree approach in POSIX Key project

Gedare Bloom gedare at rtems.org
Tue Jun 19 16:31:57 UTC 2012 

On Tue, Jun 19, 2012 at 4:59 AM, Ashi <ashi08104 at gmail.com> wrote:
>
>
> 2012/6/18 Gedare Bloom <gedare at rtems.org>
>>
>> On Sun, Jun 17, 2012 at 11:36 AM, Ashi <ashi08104 at gmail.com> wrote:
>> >
>> >
>> > 2012/6/15 Gedare Bloom <gedare at rtems.org>
>> >>
>> >> On Fri, Jun 15, 2012 at 6:02 AM, Ashi <ashi08104 at gmail.com> wrote:
>> >> > Hi, all.
>> >> > Last two weeks, I'm working on the one-rbtree approach in the POSIX
>> >> > Key
>> >> > project. There are several reasons that I start to code without
>> >> > deciding
>> >> > which approach is best(there are several approaches have been
>> >> > discussed
>> >> > before, here[0] is the summary I have done before): first, I want to
>> >> > make
>> >> > myself more clear about the problem lies behind the POSIX Key by
>> >> > coding
>> >> > first. Second, we may also need to implement several different
>> >> > approaches
>> >> > and evaluate them finally. This post is a partly summary of
>> >> > one-rbtree
>> >> > approach and also with many problems in it. By the way, after try to
>> >> > implement the one-rbtree approach, I find the approach manage POSIX
>> >> > Key
>> >> > data
>> >> > only by Object manager(also described in [0]) is really immature.
>> >> > I've
>> >> > tried
>> >> > to implemented that before starting the one-rbtree approach, however,
>> >> > I'm
>> >> > stuck and turn to one-rbtree approach.
>> >> >
>> >> Can you expand on why the object manager approach does not work?
>> >
>> > Yeah, I should explain it earlier:
>> > When I came to the Key getspecific stage of this approach, I found using
>> > object manager to manage all key's value didn't  simplify the key
>> > getspecific at all. The key getspecific interface is:
>> > void *pthread_getspecific( pthread_key_t  key )
>> > what we want to do is return the key's data by using the input key and
>> > the
>> > implicit imput the executing thread id. Now if we used object manager to
>> > manage all key's value, that is allocating one object such as:
>> > typedef struct {
>> > Object object;
>> > void *value;
>> > }
>> > then the work becomes finding a kind of mapping between input
>> > parameter(the
>> > key and executing thread id) and object.id. That can be done like the
>> > one-rbtree approah or something other. After get the object.id, we can
>> > get
>> > the value pointer by the object manager, work is done. This kind design
>> > didn't simplify anything compared with one-rbtree approach, so I give up
>> > this design. I have thought about other reason like the limitation of
>> > object
>> > number, because the number of key's value can be very large, but not
>> > clear
>> > whether that's a limitation.
>> >>
>> >> >
>> >> > There are 6 scenarios which we need deal with in POSIX key:
>> >> > 0. Key manage initialization
>> >> > 1. Key create
>> >> > 2. Key setspecific
>> >> > 3. Key getspecific
>> >> > 4. Key delete
>> >> > 5. Thread delete
>> >> >
>> >> > In the one-rbtree approach, I've done the 0~4(I've committed the code
>> >> > to
>> >> > one_rbtree branch in github repo[1]) , and the 5th thread delete
>> >> > hasn't
>> >> > been
>> >> > done, and needs more discussion(I'll list the problem below):
>> >> > 0. Key manage initialization
>> >> > I added two data structures in key.h, the POSIX_Keys_Rbtree_node is
>> >> > the
>> >> > node
>> >> > of the rbtree which holds all keys' values, and use Key and Thread_id
>> >> > member
>> >> > as rbtree key. POSIX_Keys_List_node is the node of a list which is
>> >> > used
>> >> > to
>> >> > save all nodes in one key or all nodes in one thread.
>> >> >
>> >> > typedef struct {
>> >> >   /** This field is the rbtree node structure. */
>> >> >   RBTree_Node Node;
>> >> Structure field names are usually lower-case, so "node".
>> >
>> > OK.
>> >>
>> >>
>> >> >   /** This field is the POSIX key used as an rbtree key */
>> >> >   pthread_key_t Key;
>> >> >   /** This field is the Thread id also used as an rbtree key */
>> >> >   Objects_Id Thread_id;
>> >> >   /** This field points to the POSIX key value of specific thread */
>> >> >   void *Value;
>> >> >  }  POSIX_Keys_Rbtree_node;
>> >> >
>> >> > typedef struct POSIX_Keys_List_node_ {
>> >> >   /** This field is the pointer which points to the next node in the
>> >> > list */
>> >> >   struct POSIX_Keys_List_node_ *Next;
>> >> >   /** This field is the key of list node */
>> >> >   POSIX_Keys_Rbtree_node *Rbnode;
>> >> >  }  POSIX_Keys_List_node;
>> >> >
>> >> Instead of writing your own linked list you should use RTEMS Chains
>> >> (if you need a linked list).
>> >
>> > I'll check that.
>> >>
>> >>
>> >> > and revises the POSIX_Keys_Control structure, it has a member Head,
>> >> > which
>> >> > points to the list of all node in specific key. The reason I attach a
>> >> > list
>> >> > of nodes in one key is that when key deletion happens, I can delete
>> >> > all
>> >> > the
>> >> > key nodes from the rbtree in that key by traverse the list. I wonder
>> >> > is
>> >> > there any better way to get all nodes belong one key from the rbtree?
>> >> >
>> >> Does key delete remove all the keys having the same pthread_key_t, or
>> >> only those keys belonging to the executing thread? If only the one key
>> >> needs to be removed then I don't see the need for this list at all,
>> >> you would just "extract" the one key.
>> >
>> > I think key delete will remove all the key's value having the same
>> > pthread_key_t, so we need track one key's all value. Here is the POSIX
>> > Key
>> > delete
>> >
>> > standard(http://pubs.opengroup.org/onlinepubs/009604499/functions/pthread_key_delete.html).
>> OK that does seem to say all keys should be removed having the same
>> pthread_key_t.
>>
>> > I wonder if we can search the rbtree(here every node has two keys:
>> > pthread_key_t key and Object_Id thread_id) only specify one key of two?
>> > If
>> > so, we needn't the list to keep track.
>> If you use pthread_key_t as a primary key and thread_id as a secondary
>> key for sorting, then you might be able to use rbtree_successor
>> function to iterate through the keys having identical pthread_key_t
>> and increasing values of thread_id.
>
> Great, I'll try it.
>>
>>
>> >>
>> >>
>> >> > typedef struct {
>> >> >    /** This field is the Object control structure. */
>> >> >    Objects_Control     Object;
>> >> >    /** This field is the data destructor. */
>> >> >    void (*destructor) (void *);
>> >> >    /** This field is the head of key's node list */
>> >> >    POSIX_Keys_List_node *Head;
>> >> >  }  POSIX_Keys_Control;
>> >> >
>> >> > The work during the POSIX Key manager initialization is:
>> >> > - besides the _Objects_Initialize_information, the global rbtree
>> >> > _POSIX_Keys_Rbtree is initialized to an empty rbtree.
>> >> >
>> >> > 1. Key create
>> >> > work in key create:
>> >> > - allocate the POSIX_Keys_Control object and initialize it.
>> >> >
>> >> > 2. Key setspecific
>> >> > work in key setspecific:
>> >> > - allocate a POSIX_Keys_Rbtree_node object and a POSIX_Keys_List_node
>> >> > object
>> >> > from RTEMS workspace
>> >> > - add the rbtree node to the rbtree
>> >> > - add the list node to the key's list
>> >> > problem:
>> >> > I'm not really clear about the workspace and heap memory, I just
>> >> > refer
>> >> > some
>> >> > code in other POSIX manager, all of them used _Workspace_Allocate and
>> >> > no
>> >> > malloc there. Could anyone explain the difference between them? Or is
>> >> > there
>> >> > any doc about that?
>> >> >
>> >> Workspace is for allocation of kernel objects. Not sure if there is an
>> >> explanation somewhere, although probably there ought to be...
>> >> Workspace is basically like heap (malloc), except that the workspace
>> >> is constrained in size based on application configuration. These
>> >> objects are rightly allocated from the workspace.
>> >
>> >
>> >>
>> >> > 3. Key getspecific
>> >> > work in key getspecific:
>> >> > - get the node in the rbtree
>> >> > problem:
>> >> > - I find a _Thread_Enable_dispatch() function in the current
>> >> > keygetspecfic.c
>> >> > file, and don't know what is it used for.
>> >> >
>> >> _POSIX_Keys_Get implicitly obtains a dispatch disable lock (via
>> >> Objects_Get). This is releasing the lock. If your code does not use
>> >> Objects_Get then probably it does not need to enable dispatching...
>> >> although you are likely having to protect the global rbtree somehow
>> >> with a critical section?
>> >
>> > I haven't consided any about the critical section before, I think key
>> > create
>> > and key setspecific which write something need protection, right? Is
>> > dispatch disable lock enable to do the protection?
>> >
>> I think you want ISR_Disable/Enable. Note that reading without a lock
>> would be a problem if another thread can acquire the lock and write,
>> so you need to protect any shared memory / data structure for both
>> reading and writing from concurrent access.
>>
> Very instructive to me:)
>>
>> >
>> >> 4. Key delete
>> >> work in key delete:
>> >> - deallocate all nodes of specific key by iterate the key node list,
>> >> and
>> >> then delete it from rbtree, also delete it from the list
>> >> - deallocate the POSIX_Key_Control object
>> >>
>> >>
>> >> Again unclear to me if the key delete should apply to all keys with
>> >> the same pthread_key_t or only the one for a particular thread. We
>> >> need to get an answer to this question before any decision can be made
>> >> about the best path forward.
>> >>
>> >> > 5. Thread delete
>> >> > I find when a posix thread deleted, a _POSIX_Keys_Run_destructors()
>> >> > function
>> >> > runs, then all key's data in the deleted thread is destructed. I have
>> >> > some
>> >> > idea about it, but haven't implement it. I'm thinking add the
>> >> > necessary
>> >> > information about key to the thread's API_Extensions area. Actually,
>> >> > I
>> >> > add a
>> >> > list head pointer to the POSIX_API_Control structure, the pointer
>> >> > points
>> >> > to
>> >> > a list of nodes which contains all the key's value pointer in one
>> >> > thread.
>> >> > When thread exits, we can deallocate all the key data by traverse
>> >> > this
>> >> > list
>> >> > and then delete the whole list. And we need add node to this list
>> >> > when
>> >> > key
>> >> > setspecific. When Key deletes nothing should be done on this list. I
>> >> > think
>> >> > we needn't delete key nodes of deleted thread from rbtree when thread
>> >> > deleted, and the only work should be done when thread deleted is
>> >> > deallocating the key's data in that thread, right?
>
>
> 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 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.
>
This is tricky but I think necessary. You might be able to put a chain
link in the key node to enqueue key node from the TCB while
simultaneously maintaining an rbtree node for the key node to handle
searching by pthread_key_t. So inserting a new key would require
inserting to the rbtree, and inserting to the TCB->keys_chain... When
deleting a key you would search the key in the rbtree, store pointer
next to rbtree_next, extract key node from the TCB->keys_chain,
extract key node from the rbtree, and continue while next->key ==
pthread_key_t... When deleting a thread you would iterate through the
TCB->keys_chain extracting from rbtree and chain.

> there also are some problems in my first implementation:
> - when I run the psxtest01.exe test in the testsuites, I get:
> no workspace available FAILED -- expected (resources still outstanding) got
> (successful completion)
> 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.
> - in the psxtest03.exe test, I get:
>
> *** TEST KEY 03 ***
> Init - pthread_key_create with NULL destructor - OK
> Init - pthread_create - OK
> Init - sleep - let thread run - OK
> Test_Thread - pthread_setspecific - OK
> Test_Thread - pthread_exit to run key destructors - OK
> Init - pthread_key_delete - OK
> Init - pthread_key_create with non-NULL destructor - OK
> Init - pthread_create - OK
> Init - sleep - let thread run - OK
> Test_Thread - pthread_setspecific - OK
> Test_Thread - pthread_exit to run key destructors - OK
> Init - verify destructor did NOT ran
> ../../../../../../../rtems/c/src/../../testsuites/psxtests/psxkey03/init.c:
> 100 destructor_ran == false
>
> while the original output is:
> *** TEST KEY 03 ***
> Init - pthread_key_create with NULL destructor - OK
> Init - pthread_create - OK
> Init - sleep - let thread run - OK
> Test_Thread - pthread_setspecific - OK
> Test_Thread - pthread_exit to run key destructors - OK
> Init - pthread_key_delete - OK
> Init - pthread_key_create with non-NULL destructor - OK
> Init - pthread_create - OK
> Init - sleep - let thread run - OK
> Test_Thread - pthread_setspecific - OK
> Test_Thread - pthread_exit to run key destructors - OK
> Init - verify destructor did NOT ran
> Init - pthread_key_delete - OK
> *** END OF TEST KEY 03 ***
> 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?
>
You could try to remove optimize flags from the
c/src/lib/libbsp/sparc/erc32/make/custom/erc32 --- these flags control
the optimization level for the rtems build.

>> >> >
>> >> I think a chain pointing to all of a thread's keys could work fine...
>> >> although this thread-deletion requirement makes me think that every
>> >> thread could just have an rbtree of its own keys. The overhead of an
>> >> rbtree versus a chain is not a lot, and this approach would save
>> >> having a separate list for each thread's keys. You would just use a
>> >> thread's "local" keys rbtree. I'm not sure you would even need locking
>> >> in this case... interesting.
>> >
>> > Yeah, I'm also thinking about one rbtree per thread design. I'll dig
>> > more.
>> >>
>> >>
>> >> >
>> >> > thanks for any reply on this!
>> >> >
>> >> > links:
>> >> >
>> >> >
>> >> > [0]https://docs.google.com/document/d/1orDfUJdnxbxizClFNcOVbh0t3T0vtmt5FYJETSNb6KE/edit
>> >> > [1]https://github.com/ashi08104/rtems/tree/one_rbtree#
>> >> > --
>> >> > Best wishes!
>> >> > Zhongwei Yao
>> >> >
>> >> >
>> >> > _______________________________________________
>> >> > rtems-devel mailing list
>> >> > rtems-devel at rtems.org
>> >> > http://www.rtems.org/mailman/listinfo/rtems-devel
>> >> >
>> >
>> >
>> >
>> >
>> > --
>> > Best wishes!
>> > Zhongwei Yao
>> >
>
>
>
>
> --
> Best wishes!
> Zhongwei Yao
>

More information about the devel mailing list