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

Sun Apr 1 18:21:02 UTC 2012

>From phone. I don't know how using rbtree would impact memory allocation in the sense of when allocations occur but since if the tree stays balanced, that may be a viable implementation. 

Or a hash... I know the problem and don't claim to know the perfect solution. :)

But if you use thread ids as keys, you have known properties on the values being hashed or indexed.

--joel

阿四 <ashi08104 at gmail.com> wrote:

>2012/3/31 Joel Sherrill <joel.sherrill at oarcorp.com<mailto:joel.sherrill at oarcorp.com>>
>On 03/31/2012 09:06 AM, Gedare Bloom wrote:
>On Fri, Mar 30, 2012 at 10:50 AM, 阿四<ashi08104 at gmail.com<mailto: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
>Note that the Notepads are at the end of structure. In cpukit/src/tasks.c,
>this is downsized based on how many notepads are configured. If 0,
>then no space is reserved.
>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
>
>Keys are simple from a user viewpoint so there isn't much to document. :)
>
>The issue at hand is that the Values table is an array of tables per API.
>For each API, an array of (void *) elements is allocated. When the unlimited
>allocation is tripped, the allocated array is not resized. The Values element
>needs to be replaced with a hash.
>
>If you consider unlimited keys, there is a lot of memory reserved.
>If you consider unlimited tasks/threads, then there are a lot of keys
>which need to be resized
>
>I see, it's very instructive!
>
>Hashing avoids that.  But we need reasonable performance for
>insertion, setting, getting, and deletion of a value.
>
>
>
>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
>
>OBJECTS_APIS_LAST is the number of APIs supported in RTEMS.
><null>=0, Internal=1, Classic=2, POSIX=3, and itron was = 4
>
>For each of those, you need enough pointer slots for the
>CONFIGURE_MAXIMUM_TASKS or CONFIGURE_MAXIMUM_POSIX_THREADS,
>etc.
>
>
>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.
>Exactly. You need to have keys for all tasks/threads no matter which API
>was used to create the task/thread. We want them all to be supported
>by keys.
>
>This is an example of a key feature in RTEMS. All tasks/threads
>at the API level are instances of SuperCore threads and thus
>have the same attributes. You can use Classic API services
>with POSIX threads, and POSIX API services with Classic API threads.
>
>
>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
>IMHO they are generally not useful and our current solution
>lets them consume 0 bytes so no need to address them at
>all in this project.
>
>OK, I've removed notepad related stuff in my proposal now. I should ask this more early.
>
>We couldn't do that when this idea was written up.
>
>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.
>No C++ is allowed. None at the SuperCore effort. Say that
>to yourself over and over. C++ compilable though.
>
>This is for a C implementation at the SuperCore level which
>can be used by keys and promoted out via an RTEMS specific
>API. It will need to be documented in the user's manual.
>
>Sorry, I think I didn't make myself understood. I means the final implementation may similar with std::vector, however, I should make effort to get more clear with the requirement of POSIX key to help choose proper algorithm. At my first thought, these requirement are needed in key POSIX: 1. random access to key 2. random insert and delete key. I'm not familiar with this enough, and need help to make it clear.
>And then I'll make effort to make myself be clear of the map and hash as soon as possible. I know hash basicly and familiar with using std::map, however, I'm still not quite clear with how hash and map will be appied to POSIX key. (and I think I messed hash and map up in the proposal.) Now, my idea is we could hash all the key(pthread_key_t type) to a hash array table with proper size of buckets, and then we can lookup key quickly because of keys are hashed. and of course the array table is not appropriate for dynamic expanding or shrinking, other data structure should be adopted(such as rbtree, linked-lists etc.) Maybe this is wrong, I ask help to make it right and need more detail about the whole idea.
>
>Thanks!
>--zw_yao
>
>
>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
>