<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
On 04/06/2012 11:24 AM, 阿四 wrote:
<blockquote
cite="mid:CAJnfWeGcYxQFiuBFpiUfxHWpTQzMkU3qyd3MYJtOa0hdwFqMsg@mail.gmail.com"
type="cite"><br>
<br>
<div class="gmail_quote">2012/4/6 Gedare Bloom <span dir="ltr"><<a
moz-do-not-send="true" href="mailto:gedare@rtems.org">gedare@rtems.org</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb">
<div class="h5">On Fri, Apr 6, 2012 at 11:27 AM, 阿四 <<a
moz-do-not-send="true" href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>>
wrote:<br>
><br>
><br>
> 2012/4/6 Gedare Bloom <<a moz-do-not-send="true"
href="mailto:gedare@rtems.org">gedare@rtems.org</a>><br>
>><br>
>> On Thu, Apr 5, 2012 at 12:52 PM, Joel Sherrill<br>
>> <<a moz-do-not-send="true"
href="mailto:joel.sherrill@oarcorp.com">joel.sherrill@oarcorp.com</a>>
wrote:<br>
>> > On 04/05/2012 11:09 AM, Gedare Bloom wrote:<br>
>> ><br>
>> > On Thu, Apr 5, 2012 at 10:44 AM, 阿四 <<a
moz-do-not-send="true" href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>>
wrote:<br>
>> ><br>
>> > And another idea of hash + map, if the map
part is a sub rbtree, then<br>
>> > the<br>
>> > size of hash table can be not too big, the
search operation could<br>
>> > benifit<br>
>> > from the rbtree's O(lg(n)) speed, could it
be a candidate of the<br>
>> > solution?<br>
>> ><br>
>> > You mean to use a hash-array with an rbtree
to handle collisions?<br>
>> ><br>
>> > Yeah, I mean it.<br>
>> ><br>
>> > It<br>
>> > could work, and be faster on average than
just using an rbtree without<br>
>> > losing any worst-case time. The space
overhead might be quite a bit<br>
>> > more to have multiple rbtree control headers
and also the extra<br>
>> > overhead of rbtree nodes. I think that any
rbtree- or chain-based<br>
>> > approach shifts the problem of determining
the number of Keys to be<br>
>> > the problem of determining the number of
nodes, since we cannot assume<br>
>> > that the Key data has a node embedded inside
of it.<br>
>> ><br>
>> > Gedare, I didn't quite understand this. Does
rbtree approach has the<br>
>> > problem<br>
>> > of determining the number of nodes? I think
when the key_create()<br>
>> > function<br>
>> > called, only a empty rbtree create. And when
key_setspecific() function<br>
>> > called, a node is added to rbtree. Or you
mean create a 'proper' big<br>
>> > rbtree<br>
>> > when key_create(), which frontloads the
insert node cost to key_create()<br>
>> > as<br>
>> > you mention above? I understand when using
the hash approach, determing<br>
>> > the<br>
>> > number of slots(I'm confused with the Keys
you use here, I guess Keys<br>
>> > here<br>
>> > is the slots in hash table) of hash table is
the problem of determining<br>
>> > the<br>
>> > number of nodes.<br>
>> ><br>
>> > It depends on the restrictions on key_create
and key_setspecific; if<br>
>> > creation is allowed to block/fail then
dynamic allocation might be ok.<br>
>> > I haven't looked closely enough to tell. In
that case you can create<br>
>> > an rbtree on-the-fly by allocating it when
there is a collision and<br>
>> > inserting the colliding nodes to it. You
could also just as easily use<br>
>> > a linked-list (chain). The colliding nodes
will need to be embedded<br>
>> > inside some other structure like<br>
>> > struct {<br>
>> > RBTree_Node r; // or Chain_Node<br>
>> > void * user_data;<br>
>> > }<br>
>> ><br>
>> > this structure would have to be allocated as
well whenever inserting a<br>
>> > new key (setspecific). We need to better
define the restrictions on<br>
>> > the keys in order to understand what kind of
solutions we can use.<br>
>> > Restrictions means timing and memory
constraints, whether operations<br>
>> > can block..maybe others.<br>
>> ><br>
>> ><br>
>> > <a moz-do-not-send="true"
href="http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_setspecific.html"
target="_blank">http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_setspecific.html</a><br>
>> > allows pthread_setspecific to return ENOMEM.
Is that a hint?<br>
>> ><br>
>> OK; then it just matters how 'fast' we think it
should be on avg or in<br>
>> worst-case.<br>
>><br>
>> > I don't see why we don't just put a pointer
to the Key in the tcb.<br>
>> ><br>
>> > Does it mean delete the POSIX Key data
structure, and let the Thread<br>
>> > Specific Data be managed in TCB?<br>
>> ><br>
>> > Yeah. We could define generic
thread-specific data at the score level.<br>
>> > I'm not sure if this is a good idea.<br>
>> ><br>
>> > It isn't if generic. It could be part of the
POSIX API thread extension<br>
>> > structure.<br>
>> ><br>
>> > But it helps with unlimited threads but not
with unlimited keys<br>
>> > if you use a simple array.<br>
>> ><br>
>> > But a hash/rbtree for "keys used by this
thread" might be an<br>
>> > implementation<br>
>> > option. That is different than "threads
using this key" which puts<br>
>> > the management structure in keys.<br>
>> ><br>
>> Yes that makes sense. I could see having an
rbtree of the keys in a<br>
>> posix thread extension. This would also avoid
problems with collisions<br>
>> between threads, especially since threads are
allowed to specify the<br>
>> same key for different data. Holding the keys in
separate per-thread<br>
>> structures seems the best solution. If the number
of keys is expected<br>
>> to be small then a linked list/chain would be
fine too.<br>
>><br>
> Gedare, I haven't thought about the problem of
collisions about same thread<br>
> specify the same key for different data. In current
implementation, if the<br>
> same thread specify different data in the same key by
pthread_setspecific(),<br>
> the old data is replaced by new data, isn't it? And
is it allowed? since it<br>
> would lead to memory leak. However, I find this
project can support this<br>
> kind operation by adding some index.<br>
><br>
</div>
</div>
I was unclear: different threads can use the same key for
different<br>
data. So you must be able to distinguish them. This would be
hard if<br>
all keys are managed in a single structure, but if there is a<br>
structure of keys per-thread it is less difficult.<br>
</blockquote>
<div> <br>
Sorry, Gedare, I feel a structure of keys per-thread would
make thing easy. However, I'm still confused with the hard of
all keys are managed in a single structure. I need some help
to make myself clear about key manager.<br>
<br>
First, in current implementation I know the the key is
identified by the_key->Object.id (I copy it from
keycreate.c, line 96), and the_key's type is Key_Control,
namely, the key is identified by a Object id, which is managed
by Chain Manager. So keys can be distinguished by Object id.
And for different thread data in the same key, they are
distinguished by _Thread_Executing->Object.id (this is the
current executing thread's TCB's object id). Then all things
are distinguished in current implementation.<br>
</div>
</div>
</blockquote>
Each key has a unique id and is used for a unique purpose. Think of<br>
it in terms of say a Java run-time where each Java thread is
implemented<br>
as a POSIX thread. The run-time would use a key to hold a pointer to<br>
the Java run-time specific data.<br>
<br>
So a key holds a pointer to the same type of data for the same
purpose.<br>
Each thread can have its own "instance of the library's context"<br>
<br>
No thread will have two values for the same key simultaneously.<br>
Each set operation overwrites the previous value:<br>
<br>
The scenarios of interest are:<br>
<br>
+ key create (what do do)<br>
+ key delete (clean up all references to this key)<br>
+ key get specific - should be very fast<br>
+ key set specific - not so fast because generally only<br>
done once when you initialize a thread to use<br>
a specific library<br>
+ thread delete - if key data is held in the TCB,<br>
then it needs to be freed. Clean up generally.<br>
<br>
<blockquote
cite="mid:CAJnfWeGcYxQFiuBFpiUfxHWpTQzMkU3qyd3MYJtOa0hdwFqMsg@mail.gmail.com"
type="cite">
<div class="gmail_quote">
<div>
<br>
And in this project, like in the hash approach, I think
different keys can be distinguished as before, and very key
have a member pointer to hash table, and different thread's
data in the same key is distinguish by its thread id (when in
collisions, for different thread, their data can be
distinguished by thread id again.) But for the different data
of same thread in same key, I think they need extra
information to be distinguished. <br>
<br>
Am I missed something? <br>
Or in this project, different keys can't be distinguished as
before. I feel there's may be an unacceptiable cost of lookup
with unlimited key configuration.<br>
<br>
Best Regard<br>
--zw_yao<br>
</div>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
I suspect you can just use a chain (linked list) of keys for
each<br>
thread, with the chain control (linked list head) somewhere
the thread<br>
can get to easily. Converting the Key_Control to represent a
single<br>
key instead of all keys might be an easy way to go; it already
embeds<br>
a Chain_Node and some other metadata, and the Object
allocation can<br>
deal with limits on numbers of keys.<br>
<div class="HOEnZb">
<div class="h5"><br>
>> > You also have to consider the case of
deleting threads and deleting<br>
>> > keys and what is required to clean up
outstanding memory.<br>
>> > It is simple now. But it is possible that
you have a "management<br>
>> > structure" in one object (key or thread) and
a "clean up" structure<br>
>> > on the other.<br>
>> ><br>
>> > I am sure you don't want to do a scan of all
thread/keys and<br>
>> > then see if it is impacted by a key/thread
delete.<br>
>> ><br>
>> > I hope that makes sense.<br>
>> > structure/list<br>
>> ><br>
>> ><br>
>> > -Gedare<br>
>> ><br>
>> ><br>
>> ><br>
>> > --<br>
>> > Joel Sherrill, Ph.D. Director of
Research& Development<br>
>> > <a class="moz-txt-link-abbreviated" href="mailto:joel.sherrill@OARcorp.com">joel.sherrill@OARcorp.com</a> On-Line
Applications Research<br>
>> > Ask me about RTEMS: a free RTOS Huntsville
AL 35805<br>
>> > Support Available <a
moz-do-not-send="true" href="tel:%28256%29%20722-9985"
value="+12567229985">(256) 722-9985</a><br>
>> ><br>
><br>
><br>
</div>
</div>
</blockquote>
</div>
<br>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
Joel Sherrill, Ph.D. Director of Research& Development
<a class="moz-txt-link-abbreviated" href="mailto:joel.sherrill@OARcorp.com">joel.sherrill@OARcorp.com</a> On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985
</pre>
</body>
</html>