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

Tue Jun 19 08:59:19 UTC 2012

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.

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?

>> >
> >> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20120619/7d0a4cd7/attachment-0001.html>