[GSoC]Todo in POSIX Key project

Ashi ashi08104 at gmail.com
Fri Aug 10 08:54:14 UTC 2012

I've updated the code, which fixes a bug and removes some compiler
warnings. The bug is:

diff --git a/cpukit/posix/include/rtems/posix/threadsup.h
index 5409c81..eae55aa 100644
--- a/cpukit/posix/include/rtems/posix/threadsup.h
+++ b/cpukit/posix/include/rtems/posix/threadsup.h
@@ -72,7 +72,7 @@ typedef struct {
   Chain_Control           Cancellation_Handlers;

   /** This is the thread key value chain's control */
-  Chain_Control          *the_chain;
+  Chain_Control          the_chain;

 } POSIX_API_Control;

It surprises me that this bug haven't broken any test before...Luckily, I
find it when I try to remove compiler's warning. However, there is still a
discards `const' warning at cpukit/posic/src/keysetspecific.c:52. I find
it's difficult to remove this warning, not sure whether it matters a lot.

And I've done the space comparison between one-rbtree and
one-rbtree-per-thread. It seems that I make this comparion more cumbersome
than it should be...my conlusion is both approaches need O( m * t ) memory.
Here are the details:

Suppose there is m keys and t threads, each threads have m key values, that
is there are n=m * t nodes in one-rbtree approach, and m nodes in each
rbtree in one-rbtree per-thread approach.
 - space of one rbtree approach:
S1 = m * sizeof( POSIX_Keys_Control ) + m * t * sizeof(
POSIX_Keys_Rbtree_node ) + t * sizeof( Chain_Control )
 - space of one-rbtree per-thread:
S2 = m * sizeof( POSIX_Keys_Control ) + m * t * sizeof(
POSIX_Keys_Rbtree_node ) + t * sizeof( RBTree_Control )

0. These two approach's POSIX_Keys_Control struct are the same:
typedef struct {
   Objects_Control     object;
   void (*destructor) (void *);
 }  POSIX_Keys_Control;

1. one-rbtree approach's POSIX_Keys_Rbtree_node is:

typedef struct {
  Chain_Node ch_node;
  RBTree_Node rb_node;
  pthread_key_t key;
  Objects_Id thread_id;
  void *value;
 }  POSIX_Keys_Rbtree_node;

while one-rbtree-per-thread's POSIX_Keys_Rbtree_node is like:

typedef struct {
  RBTree_Node rb_node;
  pthread_key_t key;
  void *value;
 }  POSIX_Keys_Rbtree_node;

there is no Chain_Node and Objects_Id member here. The season of include
those two members is one-rbtree approach uses a chain to keep track each
thread's key nodes. However, in one-rbtree-per-thread approach each thread
has a tree to do that work, then there is no need to include those two

3. On sparc, the sizes of these structure are:
    one-rbtree's POSIX_Keys_Rbtree_node: 36
    one-rbtree-per-thread's POSIX_Keys_Rbtree_node: 24
    Chain_Control: 12
    RBTree_Control: 24
    POSIX_Keys_Control: 20
---END of NOTE---

If take the size of these structure on Sparc as an example, the result is:
 - space of one rbtree approach:
   S1 = m * 20 + m * t * 36+ t * 12
 - space of one-rbtree per-thread:
   S2 = m * 20 + m * t * 24 + t * 24
and S1 - S2  = 12 * t * ( m - 1). The one-rbtree approach needs more
memory. However, both approaches need O( m * t ) memory.

Best wishes!
Zhongwei Yao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20120810/7ca8d90c/attachment.html>

More information about the devel mailing list