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

Mon Jun 18 15:26:15 UTC 2012

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.

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

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