= Use Hash or Map in POSIX Key =

=  Current implementation's problem  =

There are 2 problems in current implementation of POSIX Key(more details are described next section).
#The POSIX key area is not properly extended when the number of threads increases (e.g. dynamically created) if POSIX threads are configured as "unlimited", which is a known bug.
#Extra memory is reserved in keys for each thread or task in current implementation, which can be heavy memory overhead when keys increase.=  Several design approaches  =
=  Current implementation  =

current implementation allocates an array when key creates, which holds all of the threads' or tasks' key value. The pre-allocated array's size is as big as the number of threads in system. It is a waste of memory that allocates key value slot for thread which would not use POSIX key at all. And other problems of current implementation is as the current implementation's problem section describes.=  One rbtree approach  =

In this approach, there is only one rbtree which is used to manage all POSIX Keys' data. If there are '''m''' POSIX Keys and '''t''' POSIX Threads, and each Thread has '''m''' Key values, then there is '''n(n = m * t)''' nodes in the global rbtree. A comparison between this approach and one rbtree per thread approach is provided in next section.=  One rbtree per thread approach  =

Suppose there are also '''m''' POSIX Keys and '''t''' POSIX Threads in the system, then each thread maintains one rbtree, all key data of specific thread is in that rbtree. For example, say if each thread has '''m''' Key values, then there are '''m''' nodes in each thread's rbtree. The comparison between one rbtree approach and one rbtree per-thread approach is provided in next section.=  Hash approach  =

There is also a hash approach discussed before([http://www.rtems.org/pipermail/rtems-devel/2012-May/001138.html links]). However, it's worst-case runtime is '''O(n)'''. And it's unacceptable to RTEMS. Another reason that this approach is not desirable is that we would have to add hash code to RTEMS score which is not there now. The other approaches reuse a score object(the rbtree api).=  Comparison between one-rbtree and one-rbtree per-thread approach  =

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.
 *  Runtime comparison
{| class="wikitable"
|-
! operation 
! one rbtree
! one-rbtree per-thread
|-
| Key create
| O(1)
| O(1)
|-
| Key delete 
| O(t * lg(n))
| O(t * lg(m))
|-
| Setspecific
| O(lg(n))
| O(lg(m))
|-
| Getspecific
| O(lg(n))
| O(lg(m))
|-
| Thread delete
| O(m * lg(n))
| O(m * lg(m))
|}

 *  Space comparison
{| class="wikitable"
|-
! 
! one rbtree
! one-rbtree per-thread 
|-
| space 
| m * POSIX_Keys_Control + m * t * POSIX_Keys_Rbtree_node + t * Chain_Control 
| m * POSIX_Keys_Control + m * t * POSIX_Keys_Rbtree_node + t * RBTree_Control
|}
Here are some notes about the space comparison.

On sparc, the sizes of these structure are:
    one-rbtree's POSIX_Keys_Rbtree_node: 36 Bytes
    one-rbtree-per-thread's POSIX_Keys_Rbtree_node: 24 Bytes
    Chain_Control: 12 Bytes
    RBTree_Control: 24 Bytes
    POSIX_Keys_Control: 20 Bytes
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.=  the CONFIGURE of POSIX Key  =

there are 2 configuration options for POSIX Key:
        - CONFIGURE_MAXIMUM_POSIX_KEYS
        - CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS
CONFIGURE_MAXIMUM_POSIX_KEYS defines the keys numbers in system. CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS defines the key-thread (or key-task in classic API) pair numbers in system. It's used for more accurate memory control. If CONFIGURE_MAXIMUM_POSIX_KEYS is defined and CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS is not defined, then each thread (and task) would have a key value instance. For example, suppose there are 5 threads in system, and there are 3 threads need key, say they are thread1, thread2, thread3 respectively. Thread1 needs 2 keys, thread2 also needs 2 keys and thread3 only needs 1 key. Then we can define CONFIGURE_MAXIMUM_POSIX_KEYS 2 and define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS 5. If we doesn't define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS in above example, then each thread can have its own key data, this is the same as that define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS 10. So if we are sure about the number of thread would use key in system, we can define CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS to save memory. And CONFIGURE_MAXIMUM_POSIX_KEY_PAIRS <= CONFIGURE_MAXIMUM_POSIX_KEYS is an error.