2012/3/31 Joel Sherrill <span dir="ltr"><<a href="mailto:joel.sherrill@oarcorp.com">joel.sherrill@oarcorp.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On 03/31/2012 09:06 AM, Gedare Bloom wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On Fri, Mar 30, 2012 at 10:50 AM, 阿四<<a href="mailto:ashi08104@gmail.com" target="_blank">ashi08104@gmail.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi, all. I'm interesing in the hash/map in POSIX key and Classic notepad<br>
project[1] and want to apply it as my GSoC this year. I've submitted my<br>
proposal at GSoC. Here are some problems I want to figure out, thanks for<br>
reply to any of them:<br>
<br>
1. First, I want to be sure where the entry point of this project exactly is<br>
in the RTEMS. For the notepad, I think RTEMS_API_Control structure, which<br>
includes the Notepads array member, is the entry of the Notepad part of this<br>
project. And to the POSIX key, the corresponding structure is<br>
POSIX_Keys_Control structure, and the key area mentioned in [1] is the<br>
Values array member of POSIX_Keys_Control. Am I missing something?<br>
<br>
typedef struct {<br>
rtems_event_set pending_events;<br>
rtems_event_set event_condition;<br>
ASR_Information Signal;<br>
uint32_t Notepads[ RTEMS_NUMBER_NOTEPADS ];<br>
} RTEMS_API_Control;<br>
<br>
</blockquote>
Yes you have found where the fields are stored. See<br>
<a href="http://rtems.org/onlinedocs/doc-current/share/rtems/html/c_user/c_user_83.html#Task-Manager-Directives" target="_blank">http://rtems.org/onlinedocs/doc-current/share/rtems/html/c_user/c_user_83.html#Task-Manager-Directives</a><br>
6.4.12 TASK_GET_NOTE - Get task notepad entry and 6.4.13 TASK_SET_NOTE<br>
- Set task notepad entry for how the user gets at these fields<br>
</blockquote></div>
Note that the Notepads are at the end of structure. In cpukit/src/tasks.c,<br>
this is downsized based on how many notepads are configured. If 0,<br>
then no space is reserved.<br></blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
typedef struct {<br>
Objects_Control Object;<br>
void (*destructor)( void * );<br>
void **Values[ OBJECTS_APIS_LAST + 1 ];<br>
} POSIX_Keys_Control;<br>
<br>
</blockquote>
The documentation on keys is a little thin but find it here:<br>
<a href="http://rtems.org/onlinedocs/doc-current/share/rtems/html/posix_users/posix_users_368.html#Key-Manager" target="_blank">http://rtems.org/onlinedocs/doc-current/share/rtems/html/posix_users/posix_users_368.html#Key-Manager</a><br>
</blockquote>
<br></div>
Keys are simple from a user viewpoint so there isn't much to document. :)<br>
<br>
The issue at hand is that the Values table is an array of tables per API.<br>
For each API, an array of (void *) elements is allocated. When the unlimited<br>
allocation is tripped, the allocated array is not resized. The Values element<br>
needs to be replaced with a hash.<br>
<br>
If you consider unlimited keys, there is a lot of memory reserved. </blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
If you consider unlimited tasks/threads, then there are a lot of keys<br>
which need to be resized<br>
</blockquote><div> </div><div>I see, it's very instructive!<br>
<br>
</div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Hashing avoids that. But we need reasonable performance for<br>
insertion, setting, getting, and deletion of a value.<div><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2. I doesn't quite understand the key create procedure.First, I'm not sure<br>
what determines the maximum variable at line4 in code below, is it equal to<br>
CONFIGURE_MAXIMUM_POSIX_KEYS in configuration? Second, where the code also<br>
</blockquote>
It's actually the maximum number of classic or posix tasks<br>
(CONFIGURE_MAXIMUM_TASKS or POSIX_THREADS) depending on the API. this<br>
code makes use of the fact that both classic and posix APIs store the<br>
tasks at the [1] offset of their respective object table entry. It's<br>
not entirely clear, but you can see this by looking at how the table<br>
is loaded by calling _Objects_Initialize_information and that the<br>
table stores along the first dimension the apis and along the second<br>
dimension the classes (not in a matrix but in a compact vector). Look<br>
at score/include/rtems/score/object.h for the definitions of the<br>
meanings of the different APIs and their respective classes<br></blockquote></div></blockquote><div> </div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
OBJECTS_APIS_LAST is the number of APIs supported in RTEMS.<br>
<null>=0, Internal=1, Classic=2, POSIX=3, and itron was = 4<br>
<br>
For each of those, you need enough pointer slots for the<br>
CONFIGURE_MAXIMUM_TASKS or CONFIGURE_MAXIMUM_POSIX_THREADS,<br>
etc.
<div><br>
<br></div>
</blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="im">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
allocates key memory for OBJECTS_INTERNAL_API, OBJECTS_CLASSIC_API, while in<br>
my opinion, only key memory allocation for OBJECTS_POSIX_API is enough. what<br>
are other things used for?<br>
<br>
</blockquote>
I'm unsure. It appears that this will let non-posix (classic) tasks<br>
store thread-specific data using the posix key interface. Good<br>
question.<br>
</blockquote></div>
Exactly. You need to have keys for all tasks/threads no matter which API<br>
was used to create the task/thread. We want them all to be supported<br>
by keys.<br>
<br>
This is an example of a key feature in RTEMS. All tasks/threads<br>
at the API level are instances of SuperCore threads and thus<br>
have the same attributes. You can use Classic API services<br>
with POSIX threads, and POSIX API services with Classic API threads.<div><div class="h5"><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
typedef enum {<br>
OBJECTS_NO_API = 0,<br>
OBJECTS_INTERNAL_API = 1,<br>
OBJECTS_CLASSIC_API = 2,<br>
OBJECTS_POSIX_API = 3<br>
} Objects_APIs;<br>
<br>
#define OBJECTS_APIS_LAST OBJECTS_POSIX_API<br>
<br>
<br>
1 for ( the_api = 1; the_api<= OBJECTS_APIS_LAST; the_api++ ) {<br>
2 the_key->Values[ the_api ] = NULL;<br>
3<br>
4 bytes_to_allocate = sizeof( void * ) * (_Objects_Information_table[<br>
the_api ][ 1 ]->maximum + 1);<br>
5 table = _Workspace_Allocate( bytes_to_allocate );<br>
6 if ( !table ) {<br>
7 _POSIX_Keys_Free_memory( the_key );<br>
8<br>
9 _POSIX_Keys_Free( the_key );<br>
10 _Thread_Enable_dispatch();<br>
11 return ENOMEM;<br>
12 }<br>
13<br>
14 the_key->Values[ the_api ] = table;<br>
15 memset( table, '\0', bytes_to_allocate );<br>
16 }<br>
<br>
3. What's the general purpose of Notepads in RTEMS? After look at the<br>
example in /testsuites/sptests/sp07, I feel it is used for inter-thread<br>
communication, am I right? And the same question for POSIX key, since I<br>
haven't found much information of it in RTEMS POSIX API User’s Guide, I<br>
learn POSIX key knowledge from here[2], does it also apply to RTEMS?<br>
<br>
</blockquote>
Yes that is roughly the idea. Here is the standard on key create..<br>
<a href="http://pubs.opengroup.org/onlinepubs/009604499/functions/pthread_key_create.html" target="_blank">http://pubs.opengroup.org/onlinepubs/009604499/functions/pthread_key_create.html</a><br>
</blockquote></div></div>
IMHO they are generally not useful and our current solution<br>
lets them consume 0 bytes so no need to address them at<br>
all in this project.<br></blockquote><div><br>OK, I've removed notepad related stuff in my proposal now. I should ask this more early.<br> <br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
We couldn't do that when this idea was written up.<div class="im"><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
4.As mentioned in [1], std::map can be an example for this project. I<br>
wonder is std::vector also appropriate for this project? Or maybe, several<br>
differection algorithms sould be implemented, and leave the choice to user?<br>
And I haven't study hash/map algorithm in depth, maybe, I should ask related<br>
question after do more homework on this.<br>
<br>
</blockquote>
I don't think you can use functions from C++ stl for this code. We<br>
should evaluate some potential solutions and give preference to<br>
algorithms that put the time complexity cost during key creation and<br>
has fast, deterministic lookup times. The problem with just using a<br>
hash+map function is that if the hash function does not give a good<br>
distribution of keys or if the map algorithm limits the number of keys<br>
then it may be hard to put a tight bound on the lookup time in the<br>
worst-case.<br>
</blockquote></div>
No C++ is allowed. None at the SuperCore effort. Say that<br>
to yourself over and over. C++ compilable though.<br>
<br>
This is for a C implementation at the SuperCore level which<br>
can be used by keys and promoted out via an RTEMS specific<br>
API. It will need to be documented in the user's manual.<div class="im"><br></div></blockquote><div>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.
<br>And <span style="font-size:medium"> <font>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</font></span><font>. <span>(and I think I messed hash and map up in the proposal.)</span></font>
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.<br>
<br>
Thanks!<br> --zw_yao<br>
<br></div><div class="im">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
5. What's the function naming convention in RTEMS, like _POSIX_Key_Get is an<br>
inline function, while _POSIX_Keys_Free_memory is not.<br>
<br>
</blockquote>
functions that are short usually get inlined. The naming convention<br>
for internal code is (_API)_Package_name_Method_name(...), where _API<br>
is optional; for posix internals it is _POSIX. For score the _API<br>
normally is omitted (occasionally you will find something named<br>
_CORE). For the public APIs the posix routines stick to the posix<br>
standards, and the classic routines are rtems_package_method(...); the<br>
chain and red-black tree data structures public APIs are implemented<br>
in cpukit/sapi.<br>
</blockquote>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
<br>
-Gedare<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
links:<br>
[1]<a href="http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys" target="_blank">http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys</a><br>
[2]<a href="http://www.cs.cf.ac.uk/Dave/C/node29.html#SECTION002945000000000000000" target="_blank">http://www.cs.cf.ac.uk/Dave/C/node29.html#SECTION002945000000000000000</a><br>
<br>
Best Regards!<br>
zw_yao<br>
<br></blockquote></div></blockquote>