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

[Ashi]

2012/6/20 Gedare Bloom <gedare at rtems.org>

> 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.
>
Good idea, I'll try it.

>
> > 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.
>
> Great, I've tried. Now, the one-tree version can pass those tree tests.

> >> >> >
> >> >> 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
> >
>



-- 
Best wishes!
Zhongwei Yao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20120621/9f00f844/attachment-0001.html>