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

[Ashi]

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.


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;
  /** 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;

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?

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?

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.

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

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?


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