home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / quartz / quartz10.lha / src / presto / hc_slock_asm.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-02  |  8.2 KB  |  276 lines
  1. /*
  2.  *  hc_slock_asm.h
  3.  *
  4.  *  Queue-based spinlock specialized for situations where there is high
  5.  *  contention for the lock.
  6.  *
  7.  *  In a regular spinlock, all threads requesting the lock spin, performing
  8.  *  test-and-set operations on a single shared memory location.  The
  9.  *  resulting cache invalidation traffic quickly saturates the bus with
  10.  *  only a small number of spinning processors, impacting the performance
  11.  *  of the thread holding the lock (by interfering with it's ability to
  12.  *  access memory) and causing a rapid falloff in performance.
  13.  *
  14.  *  The queue-based spinlock is designed to eliminate this problem.  Threads
  15.  *  spin on a private location instead of a shared location, eliminating the
  16.  *  cache invalidation traffic.  To release a lock, the thread holding the
  17.  *  lock simply sets the private location that the next waiter is spinning on
  18.  *  (in this case no atomic instruction is needed).
  19.  *
  20.  *  Since C++ doesn't know about asm functions yet, this file gets pulled into
  21.  *  C++'s straight C output via the +hasmdefs.h C++ flag.
  22.  *
  23.  *  Depends on:
  24.  *
  25.  *  declaration of hc_slock_t in parallel.h
  26.  *  declaration of HC_Spinlock class in spinlock.h
  27.  *
  28.  *  Modification History:
  29.  *
  30.  *  28-Dec-1989  JEF
  31.  *  Integrated HC_Spinlock asm functions (after original version by raj).
  32.  *
  33.  */
  34.  
  35. /* 
  36.  * XXX Warning:
  37.  *    this will have to be changed if the structure of "thisproc"
  38.  *    changes.  for now, we "know" that the "p_pid" field is at
  39.  *    offset 24.
  40.  */
  41. #ifndef THISPROC_ID_OFFSET
  42. #define THISPROC_ID_OFFSET 24
  43. #endif THISPROC_ID_OFFSET
  44.  
  45. /*
  46.  *  HC_S_LOCK - acquire high contention spinlock.
  47.  */
  48. asm void HC_S_LOCK(laddr)
  49. {
  50. %reg laddr; lab spin, done;
  51. /PEEPOFF
  52.     /* 
  53.          * Get process id for processor on which this thread is
  54.          * running.  Convert from 0 to NUMPROCS-1 form to 1 to NUMPROCS,
  55.          * since the lock data structure uses row 0 for something special.
  56.      */
  57.     movl    _thisproc, %edx
  58.     movl    THISPROC_ID_OFFSET(%edx), %edx
  59.     incl    %edx
  60.  
  61.     /*
  62.          * We use the calulated process id (in range 1 to NUMPROCS) to index
  63.          * into the lock data structure to find our private data location (the
  64.          * location on which a thread that requests a lock after us will
  65.          * spin).
  66.          * 
  67.          * The complex addressing mode of the 'movb' below only accepts
  68.          * a byte offset of 8 (max) -- since our private location is at
  69.          * an offset of 16, double our process id.
  70.      */
  71.     addl    %edx, %edx
  72.     movl    %edx, %eax
  73.  
  74.     /*
  75.          * Load contents of this processor's private data location into
  76.          * high bits of %eax.
  77.          *
  78.          *   %ah = 16 (laddr + (2*p_pid)*8)
  79.          *       = 16 (laddr + 16*p_pid)
  80.          *       = laddr [p_pid] [16]
  81.      */
  82.     movb    16(laddr,%edx,8),%ah
  83.  
  84.     /*
  85.          * Atomically exchange entire contents of %eax with contents of
  86.          * first longword in row 0 of laddr.  Row 0 always contains info
  87.          * identifying last process to request lock.
  88.          *
  89.          * Before:
  90.          *   %ah = laddr [p_pid] [16]  (orig contents of my private data area)
  91.          *   %al = p_pid*2             (next lock requestor uses this to
  92.          *                              find CURRENT contents of my data area,
  93.          *                              spins until they are different)
  94.          * After:
  95.          *   %ah = laddr [last] [16]   (orig contents of private data area of
  96.          *                              last process to request lock)
  97.          *   %al = last_p_pid * 2      (used to find CURRENT contents of last
  98.          *                              lock requestor's private data)
  99.      */
  100.     xchgl    %eax,0(laddr)
  101.  
  102.     /*
  103.          * Move last lock requestor's process_id*2 into low bits of %edx.
  104.          * The 'cmpb' below will use this value in a complex addressing mode
  105.          * as was done above.
  106.      */
  107.     movb    %al,%dl
  108.  
  109.     /* 
  110.          * Now spin until last lock requestor is done with the lock and
  111.          * updates his private data location.  I.e., spin until original
  112.          * contents of his location (%ah) and current contents
  113.          * (laddr [last_pid] [16]) become different.  Since we are the only
  114.          * one spinning on this location, the location is in it's 'own'
  115.          * cache line, and there will be exactly one write to the location,
  116.          * cache coherency traffic is minimized.
  117.      */
  118. spin:    cmpb    %ah,16(laddr,%edx,8)
  119.     je    spin                     /* values still equal - spin */
  120.  
  121.     /*
  122.          * Values are no longer equal - so previous lock requestor must be
  123.          * done with the lock.
  124.          *
  125.          * We now own it - proceed!
  126.      */
  127. done:
  128. /PEEPON
  129. %mem laddr; lab spin, done;
  130. /PEEPOFF
  131.     /* SEE COMMENTS ABOVE */
  132.     movl    laddr,%ecx
  133.     movl    _thisproc, %edx
  134.     movl    THISPROC_ID_OFFSET(%edx), %edx
  135.     incl    %edx
  136.     addl    %edx,%edx
  137.     movl    %edx,%eax
  138.     movb    16(%ecx,%edx,8),%ah
  139.     xchgl    %eax,0(%ecx)
  140.     movb    %al,%dl
  141. spin:    cmpb    %ah,16(%ecx,%edx,8)
  142.     je    spin
  143. done:
  144. /PEEPON
  145. }
  146.  
  147. /*
  148.  *  HC_S_UNLOCK - release high contention spinlock.
  149.  */
  150. asm void HC_S_UNLOCK(laddr)
  151. {
  152. %reg laddr;
  153.     /* 
  154.          * Get processor id and convert into 1 to NUMPROCS format
  155.          * (from 0 to NUMPROCS-1).
  156.      */
  157.     movl    _thisproc, %edx
  158.     movl    THISPROC_ID_OFFSET(%edx), %edx
  159.     incl    %edx
  160.  
  161.     /*
  162.          * Find this processor's row in the lock data array (%edx = 16*p_pid).
  163.      */
  164.     shll    $4,%edx
  165.  
  166.     /*
  167.          * Increment this processor's private data location.  This allows
  168.          * anyone spinning on that location to proceed.  If no one was
  169.          * spinning (i.e., this processor was the last processor to request
  170.          * the lock), then the private data location will contain a different
  171.          * value then the original value stored in laddr [0][0], so later
  172.          * when someone does request the lock, they'll get it immediately.
  173.      */
  174.     incb    16(laddr,%edx)
  175.  
  176. %mem laddr;
  177.     /* SEE COMMENTS ABOVE */
  178.     movl    laddr, %ecx
  179.     movl    _thisproc, %edx
  180.     movl    THISPROC_ID_OFFSET(%edx), %edx
  181.     incl    %edx
  182.     shll    $4,%edx
  183.     incb    16(%ecx,%edx)
  184. }
  185.  
  186. asm HC_S_INIT_LOCK(laddr)
  187. {
  188. %reg laddr;
  189.     /* 
  190.          * The first row of the lock data array is used to store the id
  191.          * of the last processor to request the lock, as well as the contents
  192.          * of the requesting processor's private data area.
  193.          *
  194.          * Start out with 'dummy' processor 0 and a dummy data value of 0.
  195.          */
  196.     movl    $0,(laddr)
  197.  
  198.     /*
  199.          * Now set laddr [0][16] to 1.  This is 'dummy' processor 0's
  200.          * private data location.  Since this value is different than the
  201.          * original value of 0 loaded above, the first processor to request
  202.          * the lock in HC_S_LOCK will get it immediately, without spinning.
  203.      */
  204.     movb    $1,16(laddr)
  205. %mem laddr;
  206.     /* SEE COMMENTS ABOVE */
  207.     movl    laddr, %ecx
  208.     movl    $0,(%ecx)
  209.     movb    $1,16(%ecx)
  210. }
  211.  
  212. asm int HC_S_IS_LOCKED(laddr)
  213. {
  214. %reg laddr;
  215. /PEEPOFF
  216.         /*
  217.          *  Get proc_id*2 of last thread to request the lock (%al), and
  218.          *  value of that processor's private data location when lock
  219.          *  was requested (%ah).
  220.          */
  221.     movl    0(laddr),%eax     
  222.  
  223.     /* 
  224.          *  Load last_pid*2 into low bits of %edx.
  225.      */
  226.     subl    %edx,%edx          /* %edx = 0 */
  227.     movb    %al,%dl
  228.  
  229.     /*
  230.          * Use complex addressing mode (described in HC_S_LOCK) to see if
  231.          * last lock requestor's private data has changed since he requested
  232.          * the lock.  If not, then either he still has the lock, or he is
  233.          * still in the queue waiting to get the lock, and the lock is HELD.
  234.          * Otherwise, the two values are different, and the lock must be FREE.
  235.          *
  236.          *   %ah - original value of last lock requestor's private data
  237.          *   16(laddr,%edx,8) - as described in HC_S_LOCK, this is
  238.          *                      laddr [last_pid] [16], which stores the
  239.          *                      CURRENT value of last lock requestor's
  240.          *                      private data area.
  241.      */
  242.     cmpb    %ah,16(laddr,%edx,8)
  243.  
  244.     /*
  245.          *  Return indication of whether lock is held or free.
  246.          *  If equal, set %al and mask the rest of %eax to 0.
  247.          */
  248.     sete    %al
  249.     andl    $0xff,%eax
  250. /PEEPON
  251. %mem laddr;
  252. /PEEPOFF
  253.     /* SEE COMMENTS ABOVE */
  254.     movl    laddr,%ecx
  255.     movl    0(%ecx),%eax
  256.     subl    %edx,%edx
  257.     movb    %al,%dl
  258.     cmpb    %ah,16(%ecx,%edx,8)
  259.     sete    %al
  260.     andl    $0xff,%eax
  261. /PEEPON
  262. }
  263.  
  264.  
  265. /* XXX UNIMPLEMENTED -- should never be called */
  266. /* always return FALSE */
  267. asm int HC_S_CLOCK(laddr)
  268. {
  269. %reg laddr;
  270.     movl    $L_FAILED, %eax
  271. %mem laddr; lab spin, failed, done;
  272.     movl    $L_FAILED, %eax
  273. done:
  274. /PEEPON
  275. }
  276.