[GSoC]use hash/map in POSIX key and Classic notepad
Joel Sherrill
joel.sherrill at OARcorp.com
Sat Mar 31 14:30:41 UTC 2012
On 03/31/2012 09:06 AM, Gedare Bloom wrote:
> 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
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.
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.
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.
>
>> 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.
And in this case Key vs Keys indicates a mistake. Both are
part of POSIX Keys.
Inlining rules generally focus on performance, readability,
proper typing, and not making testing harder. Inlining a method
with many if expressions leads to test case explosion and
is bad.
--joel
>
> -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
>>
> _______________________________________________
> rtems-users mailing list
> rtems-users at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-users
--
Joel Sherrill, Ph.D. Director of Research& Development
joel.sherrill at OARcorp.com On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985
More information about the users
mailing list