<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>