[GSoC]use hash/map in POSIX key and Classic notepad

[Gedare Bloom]

On Fri, Mar 30, 2012 at 10:50 AM, 阿四 <ashi08104 at gmail.com> wrote:
> Hi, all. I'm interesing in the hash/map in POSIX key and Classic notepad
> project[1] and want to apply it as my GSoC this year. I've submitted my
> proposal at GSoC. Here are some problems I want to figure out, thanks for
> reply to any of them:
>
> 1. First, I want to be sure where the entry point of this project exactly is
> in the RTEMS. For the notepad, I think RTEMS_API_Control structure, which
> includes the Notepads array member, is the entry of the Notepad part of this
> project. And to the POSIX key, the corresponding structure is
> POSIX_Keys_Control structure, and the key area mentioned in [1] is the
> Values array member of POSIX_Keys_Control. Am I missing something?
>
> typedef struct {
>   rtems_event_set          pending_events;
>   rtems_event_set          event_condition;
>   ASR_Information          Signal;
>   uint32_t                 Notepads[ RTEMS_NUMBER_NOTEPADS ];
> }  RTEMS_API_Control;
>
Yes you have found where the fields are stored. See
http://rtems.org/onlinedocs/doc-current/share/rtems/html/c_user/c_user_83.html#Task-Manager-Directives
6.4.12 TASK_GET_NOTE - Get task notepad entry and 6.4.13 TASK_SET_NOTE
- Set task notepad entry for how the user gets at these fields

> typedef struct {
>    Objects_Control     Object;
>    void              (*destructor)( void * );
>    void              **Values[ OBJECTS_APIS_LAST + 1 ];
> }  POSIX_Keys_Control;
>
The documentation on keys is a little thin but find it here:
http://rtems.org/onlinedocs/doc-current/share/rtems/html/posix_users/posix_users_368.html#Key-Manager

> 2. I doesn't quite understand the key create procedure.First, I'm not sure
> what determines the maximum variable at line4 in code below, is it equal to
> CONFIGURE_MAXIMUM_POSIX_KEYS in configuration? Second, where the code also
It's actually the maximum number of classic or posix tasks
(CONFIGURE_MAXIMUM_TASKS or POSIX_THREADS) depending on the API. this
code makes use of the fact that both classic and posix APIs store the
tasks at the [1] offset of their respective object table entry. It's
not entirely clear, but you can see this by looking at how the table
is loaded by calling _Objects_Initialize_information and that the
table stores along the first dimension the apis and along the second
dimension the classes (not in a matrix but in a compact vector). Look
at score/include/rtems/score/object.h for the definitions of the
meanings of the different APIs and their respective classes.

> allocates key memory for OBJECTS_INTERNAL_API, OBJECTS_CLASSIC_API, while in
> my opinion, only key memory allocation for OBJECTS_POSIX_API is enough. what
> are other things used for?
>
I'm unsure. It appears that this will let non-posix (classic) tasks
store thread-specific data using the posix key interface. Good
question.

> typedef enum {
>   OBJECTS_NO_API       = 0,
>   OBJECTS_INTERNAL_API = 1,
>   OBJECTS_CLASSIC_API  = 2,
>   OBJECTS_POSIX_API    = 3
> } Objects_APIs;
>
> #define OBJECTS_APIS_LAST OBJECTS_POSIX_API
>
>
> 1   for ( the_api = 1; the_api <= OBJECTS_APIS_LAST; the_api++ ) {
> 2     the_key->Values[ the_api ] = NULL;
> 3
> 4     bytes_to_allocate = sizeof( void * ) * (_Objects_Information_table[
> the_api ][ 1 ]->maximum + 1);
> 5     table = _Workspace_Allocate( bytes_to_allocate );
> 6     if ( !table ) {
> 7       _POSIX_Keys_Free_memory( the_key );
> 8
> 9       _POSIX_Keys_Free( the_key );
> 10      _Thread_Enable_dispatch();
> 11     return ENOMEM;
> 12    }
> 13
> 14    the_key->Values[ the_api ] = table;
> 15   memset( table, '\0', bytes_to_allocate );
> 16  }
>
> 3. What's the general purpose of Notepads in RTEMS? After look at the
> example in /testsuites/sptests/sp07, I feel it is used for inter-thread
> communication, am I right? And the same question for POSIX key, since I
> haven't found much information of it in RTEMS POSIX API User’s Guide, I
> learn POSIX key knowledge from here[2], does it also apply to RTEMS?
>
Yes that is roughly the idea. Here is the standard on key create..
http://pubs.opengroup.org/onlinepubs/009604499/functions/pthread_key_create.html

> 4.As mentioned in [1], std::map can be  an example for this project. I
> wonder is std::vector also appropriate for this project? Or maybe, several
> differection algorithms sould be implemented, and leave the choice to user?
> And I haven't study hash/map algorithm in depth, maybe, I should ask related
> question after do more homework on this.
>
I don't think you can use functions from C++ stl for this code. We
should evaluate some potential solutions and give preference to
algorithms that put the time complexity cost during key creation and
has fast, deterministic lookup times. The problem with just using a
hash+map function is that if the hash function does not give a good
distribution of keys or if the map algorithm limits the number of keys
then it may be hard to put a tight bound on the lookup time in the
worst-case.

> 5. What's the function naming convention in RTEMS, like _POSIX_Key_Get is an
> inline function, while _POSIX_Keys_Free_memory is not.
>
functions that are short usually get inlined. The naming convention
for internal code is (_API)_Package_name_Method_name(...), where _API
is optional; for posix internals it is _POSIX. For score the _API
normally is omitted (occasionally you will find something named
_CORE). For the public APIs the posix routines stick to the posix
standards, and the classic routines are rtems_package_method(...); the
chain and red-black tree data structures public APIs are implemented
in cpukit/sapi.

-Gedare
>
> links:
> [1]http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys
> [2]http://www.cs.cf.ac.uk/Dave/C/node29.html#SECTION002945000000000000000
>
> Best Regards!
> zw_yao
>
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
>