Back to index

glibc  2.9
spinlock.c
Go to the documentation of this file.
00001 /* Linuxthreads - a simple clone()-based implementation of Posix        */
00002 /* threads for Linux.                                                   */
00003 /* Copyright (C) 1998 Xavier Leroy (Xavier.Leroy@inria.fr)              */
00004 /*                                                                      */
00005 /* This program is free software; you can redistribute it and/or        */
00006 /* modify it under the terms of the GNU Library General Public License  */
00007 /* as published by the Free Software Foundation; either version 2       */
00008 /* of the License, or (at your option) any later version.               */
00009 /*                                                                      */
00010 /* This program is distributed in the hope that it will be useful,      */
00011 /* but WITHOUT ANY WARRANTY; without even the implied warranty of       */
00012 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the        */
00013 /* GNU Library General Public License for more details.                 */
00014 
00015 /* Internal locks */
00016 
00017 #include <errno.h>
00018 #include <sched.h>
00019 #include <time.h>
00020 #include <stdlib.h>
00021 #include <limits.h>
00022 #include "pthread.h"
00023 #include "internals.h"
00024 #include "spinlock.h"
00025 #include "restart.h"
00026 
00027 static void __pthread_acquire(int * spinlock);
00028 
00029 static inline void __pthread_release(int * spinlock)
00030 {
00031   WRITE_MEMORY_BARRIER();
00032   *spinlock = __LT_SPINLOCK_INIT;
00033   __asm __volatile ("" : "=m" (*spinlock) : "m" (*spinlock));
00034 }
00035 
00036 
00037 /* The status field of a spinlock is a pointer whose least significant
00038    bit is a locked flag.
00039 
00040    Thus the field values have the following meanings:
00041 
00042    status == 0:       spinlock is free
00043    status == 1:       spinlock is taken; no thread is waiting on it
00044 
00045    (status & 1) == 1: spinlock is taken and (status & ~1L) is a
00046                       pointer to the first waiting thread; other
00047                     waiting threads are linked via the p_nextlock
00048                     field.
00049    (status & 1) == 0: same as above, but spinlock is not taken.
00050 
00051    The waiting list is not sorted by priority order.
00052    Actually, we always insert at top of list (sole insertion mode
00053    that can be performed without locking).
00054    For __pthread_unlock, we perform a linear search in the list
00055    to find the highest-priority, oldest waiting thread.
00056    This is safe because there are no concurrent __pthread_unlock
00057    operations -- only the thread that locked the mutex can unlock it. */
00058 
00059 
00060 void internal_function __pthread_lock(struct _pthread_fastlock * lock,
00061                                   pthread_descr self)
00062 {
00063 #if defined HAS_COMPARE_AND_SWAP
00064   long oldstatus, newstatus;
00065   int successful_seizure, spurious_wakeup_count;
00066   int spin_count;
00067 #endif
00068 
00069 #if defined TEST_FOR_COMPARE_AND_SWAP
00070   if (!__pthread_has_cas)
00071 #endif
00072 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00073   {
00074     __pthread_acquire(&lock->__spinlock);
00075     return;
00076   }
00077 #endif
00078 
00079 #if defined HAS_COMPARE_AND_SWAP
00080   /* First try it without preparation.  Maybe it's a completely
00081      uncontested lock.  */
00082   if (lock->__status == 0 && __compare_and_swap (&lock->__status, 0, 1))
00083     return;
00084 
00085   spurious_wakeup_count = 0;
00086   spin_count = 0;
00087 
00088   /* On SMP, try spinning to get the lock. */
00089 
00090   if (__pthread_smp_kernel) {
00091     int max_count = lock->__spinlock * 2 + 10;
00092 
00093     if (max_count > MAX_ADAPTIVE_SPIN_COUNT)
00094       max_count = MAX_ADAPTIVE_SPIN_COUNT;
00095 
00096     for (spin_count = 0; spin_count < max_count; spin_count++) {
00097       if (((oldstatus = lock->__status) & 1) == 0) {
00098        if(__compare_and_swap(&lock->__status, oldstatus, oldstatus | 1))
00099        {
00100          if (spin_count)
00101            lock->__spinlock += (spin_count - lock->__spinlock) / 8;
00102          READ_MEMORY_BARRIER();
00103          return;
00104        }
00105       }
00106 #ifdef BUSY_WAIT_NOP
00107       BUSY_WAIT_NOP;
00108 #endif
00109       __asm __volatile ("" : "=m" (lock->__status) : "m" (lock->__status));
00110     }
00111 
00112     lock->__spinlock += (spin_count - lock->__spinlock) / 8;
00113   }
00114 
00115 again:
00116 
00117   /* No luck, try once more or suspend. */
00118 
00119   do {
00120     oldstatus = lock->__status;
00121     successful_seizure = 0;
00122 
00123     if ((oldstatus & 1) == 0) {
00124       newstatus = oldstatus | 1;
00125       successful_seizure = 1;
00126     } else {
00127       if (self == NULL)
00128        self = thread_self();
00129       newstatus = (long) self | 1;
00130     }
00131 
00132     if (self != NULL) {
00133       THREAD_SETMEM(self, p_nextlock, (pthread_descr) (oldstatus));
00134       /* Make sure the store in p_nextlock completes before performing
00135          the compare-and-swap */
00136       MEMORY_BARRIER();
00137     }
00138   } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
00139 
00140   /* Suspend with guard against spurious wakeup.
00141      This can happen in pthread_cond_timedwait_relative, when the thread
00142      wakes up due to timeout and is still on the condvar queue, and then
00143      locks the queue to remove itself. At that point it may still be on the
00144      queue, and may be resumed by a condition signal. */
00145 
00146   if (!successful_seizure) {
00147     for (;;) {
00148       suspend(self);
00149       if (self->p_nextlock != NULL) {
00150        /* Count resumes that don't belong to us. */
00151        spurious_wakeup_count++;
00152        continue;
00153       }
00154       break;
00155     }
00156     goto again;
00157   }
00158 
00159   /* Put back any resumes we caught that don't belong to us. */
00160   while (spurious_wakeup_count--)
00161     restart(self);
00162 
00163   READ_MEMORY_BARRIER();
00164 #endif
00165 }
00166 
00167 int __pthread_unlock(struct _pthread_fastlock * lock)
00168 {
00169 #if defined HAS_COMPARE_AND_SWAP
00170   long oldstatus;
00171   pthread_descr thr, * ptr, * maxptr;
00172   int maxprio;
00173 #endif
00174 
00175 #if defined TEST_FOR_COMPARE_AND_SWAP
00176   if (!__pthread_has_cas)
00177 #endif
00178 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00179   {
00180     __pthread_release(&lock->__spinlock);
00181     return 0;
00182   }
00183 #endif
00184 
00185 #if defined HAS_COMPARE_AND_SWAP
00186   WRITE_MEMORY_BARRIER();
00187 
00188 again:
00189   while ((oldstatus = lock->__status) == 1) {
00190     if (__compare_and_swap_with_release_semantics(&lock->__status,
00191        oldstatus, 0))
00192       return 0;
00193   }
00194 
00195   /* Find thread in waiting queue with maximal priority */
00196   ptr = (pthread_descr *) &lock->__status;
00197   thr = (pthread_descr) (oldstatus & ~1L);
00198   maxprio = 0;
00199   maxptr = ptr;
00200 
00201   /* Before we iterate over the wait queue, we need to execute
00202      a read barrier, otherwise we may read stale contents of nodes that may
00203      just have been inserted by other processors. One read barrier is enough to
00204      ensure we have a stable list; we don't need one for each pointer chase
00205      through the list, because we are the owner of the lock; other threads
00206      can only add nodes at the front; if a front node is consistent,
00207      the ones behind it must also be. */
00208 
00209   READ_MEMORY_BARRIER();
00210 
00211   while (thr != 0) {
00212     if (thr->p_priority >= maxprio) {
00213       maxptr = ptr;
00214       maxprio = thr->p_priority;
00215     }
00216     ptr = &(thr->p_nextlock);
00217     thr = (pthread_descr)((long)(thr->p_nextlock) & ~1L);
00218   }
00219 
00220   /* Remove max prio thread from waiting list. */
00221   if (maxptr == (pthread_descr *) &lock->__status) {
00222     /* If max prio thread is at head, remove it with compare-and-swap
00223        to guard against concurrent lock operation. This removal
00224        also has the side effect of marking the lock as released
00225        because the new status comes from thr->p_nextlock whose
00226        least significant bit is clear. */
00227     thr = (pthread_descr) (oldstatus & ~1L);
00228     if (! __compare_and_swap_with_release_semantics
00229            (&lock->__status, oldstatus, (long)(thr->p_nextlock) & ~1L))
00230       goto again;
00231   } else {
00232     /* No risk of concurrent access, remove max prio thread normally.
00233        But in this case we must also flip the least significant bit
00234        of the status to mark the lock as released. */
00235     thr = (pthread_descr)((long)*maxptr & ~1L);
00236     *maxptr = thr->p_nextlock;
00237 
00238     /* Ensure deletion from linked list completes before we
00239        release the lock. */
00240     WRITE_MEMORY_BARRIER();
00241 
00242     do {
00243       oldstatus = lock->__status;
00244     } while (!__compare_and_swap_with_release_semantics(&lock->__status,
00245             oldstatus, oldstatus & ~1L));
00246   }
00247 
00248   /* Wake up the selected waiting thread. Woken thread can check
00249      its own p_nextlock field for NULL to detect that it has been removed. No
00250      barrier is needed here, since restart() and suspend() take
00251      care of memory synchronization. */
00252 
00253   thr->p_nextlock = NULL;
00254   restart(thr);
00255 
00256   return 0;
00257 #endif
00258 }
00259 
00260 /*
00261  * Alternate fastlocks do not queue threads directly. Instead, they queue
00262  * these wait queue node structures. When a timed wait wakes up due to
00263  * a timeout, it can leave its wait node in the queue (because there
00264  * is no safe way to remove from the quue). Some other thread will
00265  * deallocate the abandoned node.
00266  */
00267 
00268 
00269 struct wait_node {
00270   struct wait_node *next;   /* Next node in null terminated linked list */
00271   pthread_descr thr;        /* The thread waiting with this node */
00272   int abandoned;            /* Atomic flag */
00273 };
00274 
00275 static long wait_node_free_list;
00276 static int wait_node_free_list_spinlock;
00277 
00278 /* Allocate a new node from the head of the free list using an atomic
00279    operation, or else using malloc if that list is empty.  A fundamental
00280    assumption here is that we can safely access wait_node_free_list->next.
00281    That's because we never free nodes once we allocate them, so a pointer to a
00282    node remains valid indefinitely. */
00283 
00284 static struct wait_node *wait_node_alloc(void)
00285 {
00286     struct wait_node *new_node = 0;
00287 
00288     __pthread_acquire(&wait_node_free_list_spinlock);
00289     if (wait_node_free_list != 0) {
00290       new_node = (struct wait_node *) wait_node_free_list;
00291       wait_node_free_list = (long) new_node->next;
00292     }
00293     WRITE_MEMORY_BARRIER();
00294     __pthread_release(&wait_node_free_list_spinlock);
00295 
00296     if (new_node == 0)
00297       return malloc(sizeof *wait_node_alloc());
00298 
00299     return new_node;
00300 }
00301 
00302 /* Return a node to the head of the free list using an atomic
00303    operation. */
00304 
00305 static void wait_node_free(struct wait_node *wn)
00306 {
00307     __pthread_acquire(&wait_node_free_list_spinlock);
00308     wn->next = (struct wait_node *) wait_node_free_list;
00309     wait_node_free_list = (long) wn;
00310     WRITE_MEMORY_BARRIER();
00311     __pthread_release(&wait_node_free_list_spinlock);
00312     return;
00313 }
00314 
00315 #if defined HAS_COMPARE_AND_SWAP
00316 
00317 /* Remove a wait node from the specified queue.  It is assumed
00318    that the removal takes place concurrently with only atomic insertions at the
00319    head of the queue. */
00320 
00321 static void wait_node_dequeue(struct wait_node **pp_head,
00322                            struct wait_node **pp_node,
00323                            struct wait_node *p_node)
00324 {
00325   /* If the node is being deleted from the head of the
00326      list, it must be deleted using atomic compare-and-swap.
00327      Otherwise it can be deleted in the straightforward way. */
00328 
00329   if (pp_node == pp_head) {
00330     /* We don't need a read barrier between these next two loads,
00331        because it is assumed that the caller has already ensured
00332        the stability of *p_node with respect to p_node. */
00333 
00334     long oldvalue = (long) p_node;
00335     long newvalue = (long) p_node->next;
00336 
00337     if (__compare_and_swap((long *) pp_node, oldvalue, newvalue))
00338       return;
00339 
00340     /* Oops! Compare and swap failed, which means the node is
00341        no longer first. We delete it using the ordinary method.  But we don't
00342        know the identity of the node which now holds the pointer to the node
00343        being deleted, so we must search from the beginning. */
00344 
00345     for (pp_node = pp_head; p_node != *pp_node; ) {
00346       pp_node = &(*pp_node)->next;
00347       READ_MEMORY_BARRIER(); /* Stabilize *pp_node for next iteration. */
00348     }
00349   }
00350 
00351   *pp_node = p_node->next;
00352   return;
00353 }
00354 
00355 #endif
00356 
00357 void __pthread_alt_lock(struct _pthread_fastlock * lock,
00358                       pthread_descr self)
00359 {
00360 #if defined HAS_COMPARE_AND_SWAP
00361   long oldstatus, newstatus;
00362 #endif
00363   struct wait_node wait_node;
00364 
00365 #if defined TEST_FOR_COMPARE_AND_SWAP
00366   if (!__pthread_has_cas)
00367 #endif
00368 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00369   {
00370     int suspend_needed = 0;
00371     __pthread_acquire(&lock->__spinlock);
00372 
00373     if (lock->__status == 0)
00374       lock->__status = 1;
00375     else {
00376       if (self == NULL)
00377        self = thread_self();
00378 
00379       wait_node.abandoned = 0;
00380       wait_node.next = (struct wait_node *) lock->__status;
00381       wait_node.thr = self;
00382       lock->__status = (long) &wait_node;
00383       suspend_needed = 1;
00384     }
00385 
00386     __pthread_release(&lock->__spinlock);
00387 
00388     if (suspend_needed)
00389       suspend (self);
00390     return;
00391   }
00392 #endif
00393 
00394 #if defined HAS_COMPARE_AND_SWAP
00395   do {
00396     oldstatus = lock->__status;
00397     if (oldstatus == 0) {
00398       newstatus = 1;
00399     } else {
00400       if (self == NULL)
00401        self = thread_self();
00402       wait_node.thr = self;
00403       newstatus = (long) &wait_node;
00404     }
00405     wait_node.abandoned = 0;
00406     wait_node.next = (struct wait_node *) oldstatus;
00407     /* Make sure the store in wait_node.next completes before performing
00408        the compare-and-swap */
00409     MEMORY_BARRIER();
00410   } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
00411 
00412   /* Suspend. Note that unlike in __pthread_lock, we don't worry
00413      here about spurious wakeup. That's because this lock is not
00414      used in situations where that can happen; the restart can
00415      only come from the previous lock owner. */
00416 
00417   if (oldstatus != 0)
00418     suspend(self);
00419 
00420   READ_MEMORY_BARRIER();
00421 #endif
00422 }
00423 
00424 /* Timed-out lock operation; returns 0 to indicate timeout. */
00425 
00426 int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
00427                          pthread_descr self, const struct timespec *abstime)
00428 {
00429   long oldstatus = 0;
00430 #if defined HAS_COMPARE_AND_SWAP
00431   long newstatus;
00432 #endif
00433   struct wait_node *p_wait_node = wait_node_alloc();
00434 
00435   /* Out of memory, just give up and do ordinary lock. */
00436   if (p_wait_node == 0) {
00437     __pthread_alt_lock(lock, self);
00438     return 1;
00439   }
00440 
00441 #if defined TEST_FOR_COMPARE_AND_SWAP
00442   if (!__pthread_has_cas)
00443 #endif
00444 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00445   {
00446     __pthread_acquire(&lock->__spinlock);
00447 
00448     if (lock->__status == 0)
00449       lock->__status = 1;
00450     else {
00451       if (self == NULL)
00452        self = thread_self();
00453 
00454       p_wait_node->abandoned = 0;
00455       p_wait_node->next = (struct wait_node *) lock->__status;
00456       p_wait_node->thr = self;
00457       lock->__status = (long) p_wait_node;
00458       oldstatus = 1; /* force suspend */
00459     }
00460 
00461     __pthread_release(&lock->__spinlock);
00462     goto suspend;
00463   }
00464 #endif
00465 
00466 #if defined HAS_COMPARE_AND_SWAP
00467   do {
00468     oldstatus = lock->__status;
00469     if (oldstatus == 0) {
00470       newstatus = 1;
00471     } else {
00472       if (self == NULL)
00473        self = thread_self();
00474       p_wait_node->thr = self;
00475       newstatus = (long) p_wait_node;
00476     }
00477     p_wait_node->abandoned = 0;
00478     p_wait_node->next = (struct wait_node *) oldstatus;
00479     /* Make sure the store in wait_node.next completes before performing
00480        the compare-and-swap */
00481     MEMORY_BARRIER();
00482   } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
00483 #endif
00484 
00485 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00486   suspend:
00487 #endif
00488 
00489   /* If we did not get the lock, do a timed suspend. If we wake up due
00490      to a timeout, then there is a race; the old lock owner may try
00491      to remove us from the queue. This race is resolved by us and the owner
00492      doing an atomic testandset() to change the state of the wait node from 0
00493      to 1. If we succeed, then it's a timeout and we abandon the node in the
00494      queue. If we fail, it means the owner gave us the lock. */
00495 
00496   if (oldstatus != 0) {
00497     if (timedsuspend(self, abstime) == 0) {
00498       if (!testandset(&p_wait_node->abandoned))
00499        return 0; /* Timeout! */
00500 
00501       /* Eat oustanding resume from owner, otherwise wait_node_free() below
00502         will race with owner's wait_node_dequeue(). */
00503       suspend(self);
00504     }
00505   }
00506 
00507   wait_node_free(p_wait_node);
00508 
00509   READ_MEMORY_BARRIER();
00510 
00511   return 1; /* Got the lock! */
00512 }
00513 
00514 void __pthread_alt_unlock(struct _pthread_fastlock *lock)
00515 {
00516   struct wait_node *p_node, **pp_node, *p_max_prio, **pp_max_prio;
00517   struct wait_node ** const pp_head = (struct wait_node **) &lock->__status;
00518   int maxprio;
00519 
00520   WRITE_MEMORY_BARRIER();
00521 
00522 #if defined TEST_FOR_COMPARE_AND_SWAP
00523   if (!__pthread_has_cas)
00524 #endif
00525 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00526   {
00527     __pthread_acquire(&lock->__spinlock);
00528   }
00529 #endif
00530 
00531   while (1) {
00532 
00533   /* If no threads are waiting for this lock, try to just
00534      atomically release it. */
00535 #if defined TEST_FOR_COMPARE_AND_SWAP
00536     if (!__pthread_has_cas)
00537 #endif
00538 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00539     {
00540       if (lock->__status == 0 || lock->__status == 1) {
00541        lock->__status = 0;
00542        break;
00543       }
00544     }
00545 #endif
00546 
00547 #if defined TEST_FOR_COMPARE_AND_SWAP
00548     else
00549 #endif
00550 
00551 #if defined HAS_COMPARE_AND_SWAP
00552     {
00553       long oldstatus = lock->__status;
00554       if (oldstatus == 0 || oldstatus == 1) {
00555        if (__compare_and_swap_with_release_semantics (&lock->__status, oldstatus, 0))
00556          break;
00557        else
00558          continue;
00559       }
00560     }
00561 #endif
00562 
00563     /* Process the entire queue of wait nodes. Remove all abandoned
00564        wait nodes and put them into the global free queue, and
00565        remember the one unabandoned node which refers to the thread
00566        having the highest priority. */
00567 
00568     pp_max_prio = pp_node = pp_head;
00569     p_max_prio = p_node = *pp_head;
00570     maxprio = INT_MIN;
00571 
00572     READ_MEMORY_BARRIER(); /* Prevent access to stale data through p_node */
00573 
00574     while (p_node != (struct wait_node *) 1) {
00575       int prio;
00576 
00577       if (p_node->abandoned) {
00578        /* Remove abandoned node. */
00579 #if defined TEST_FOR_COMPARE_AND_SWAP
00580        if (!__pthread_has_cas)
00581 #endif
00582 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00583          *pp_node = p_node->next;
00584 #endif
00585 #if defined TEST_FOR_COMPARE_AND_SWAP
00586        else
00587 #endif
00588 #if defined HAS_COMPARE_AND_SWAP
00589          wait_node_dequeue(pp_head, pp_node, p_node);
00590 #endif
00591        wait_node_free(p_node);
00592        /* Note that the next assignment may take us to the beginning
00593           of the queue, to newly inserted nodes, if pp_node == pp_head.
00594           In that case we need a memory barrier to stabilize the first of
00595           these new nodes. */
00596        p_node = *pp_node;
00597        if (pp_node == pp_head)
00598          READ_MEMORY_BARRIER(); /* No stale reads through p_node */
00599        continue;
00600       } else if ((prio = p_node->thr->p_priority) >= maxprio) {
00601        /* Otherwise remember it if its thread has a higher or equal priority
00602           compared to that of any node seen thus far. */
00603        maxprio = prio;
00604        pp_max_prio = pp_node;
00605        p_max_prio = p_node;
00606       }
00607 
00608       /* This canno6 jump backward in the list, so no further read
00609          barrier is needed. */
00610       pp_node = &p_node->next;
00611       p_node = *pp_node;
00612     }
00613 
00614     /* If all threads abandoned, go back to top */
00615     if (maxprio == INT_MIN)
00616       continue;
00617 
00618     ASSERT (p_max_prio != (struct wait_node *) 1);
00619 
00620     /* Now we want to to remove the max priority thread's wait node from
00621        the list. Before we can do this, we must atomically try to change the
00622        node's abandon state from zero to nonzero. If we succeed, that means we
00623        have the node that we will wake up. If we failed, then it means the
00624        thread timed out and abandoned the node in which case we repeat the
00625        whole unlock operation. */
00626 
00627     if (!testandset(&p_max_prio->abandoned)) {
00628 #if defined TEST_FOR_COMPARE_AND_SWAP
00629       if (!__pthread_has_cas)
00630 #endif
00631 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00632        *pp_max_prio = p_max_prio->next;
00633 #endif
00634 #if defined TEST_FOR_COMPARE_AND_SWAP
00635       else
00636 #endif
00637 #if defined HAS_COMPARE_AND_SWAP
00638        wait_node_dequeue(pp_head, pp_max_prio, p_max_prio);
00639 #endif
00640 
00641       /* Release the spinlock before restarting.  */
00642 #if defined TEST_FOR_COMPARE_AND_SWAP
00643       if (!__pthread_has_cas)
00644 #endif
00645 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00646        {
00647          __pthread_release(&lock->__spinlock);
00648        }
00649 #endif
00650 
00651       restart(p_max_prio->thr);
00652 
00653       return;
00654     }
00655   }
00656 
00657 #if defined TEST_FOR_COMPARE_AND_SWAP
00658   if (!__pthread_has_cas)
00659 #endif
00660 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00661   {
00662     __pthread_release(&lock->__spinlock);
00663   }
00664 #endif
00665 }
00666 
00667 
00668 /* Compare-and-swap emulation with a spinlock */
00669 
00670 #ifdef TEST_FOR_COMPARE_AND_SWAP
00671 int __pthread_has_cas = 0;
00672 #endif
00673 
00674 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
00675 
00676 int __pthread_compare_and_swap(long * ptr, long oldval, long newval,
00677                                int * spinlock)
00678 {
00679   int res;
00680 
00681   __pthread_acquire(spinlock);
00682 
00683   if (*ptr == oldval) {
00684     *ptr = newval; res = 1;
00685   } else {
00686     res = 0;
00687   }
00688 
00689   __pthread_release(spinlock);
00690 
00691   return res;
00692 }
00693 
00694 #endif
00695 
00696 /* The retry strategy is as follows:
00697    - We test and set the spinlock MAX_SPIN_COUNT times, calling
00698      sched_yield() each time.  This gives ample opportunity for other
00699      threads with priority >= our priority to make progress and
00700      release the spinlock.
00701    - If a thread with priority < our priority owns the spinlock,
00702      calling sched_yield() repeatedly is useless, since we're preventing
00703      the owning thread from making progress and releasing the spinlock.
00704      So, after MAX_SPIN_LOCK attemps, we suspend the calling thread
00705      using nanosleep().  This again should give time to the owning thread
00706      for releasing the spinlock.
00707      Notice that the nanosleep() interval must not be too small,
00708      since the kernel does busy-waiting for short intervals in a realtime
00709      process (!).  The smallest duration that guarantees thread
00710      suspension is currently 2ms.
00711    - When nanosleep() returns, we try again, doing MAX_SPIN_COUNT
00712      sched_yield(), then sleeping again if needed. */
00713 
00714 static void __pthread_acquire(int * spinlock)
00715 {
00716   int cnt = 0;
00717   struct timespec tm;
00718 
00719   READ_MEMORY_BARRIER();
00720 
00721   while (testandset(spinlock)) {
00722     if (cnt < MAX_SPIN_COUNT) {
00723       sched_yield();
00724       cnt++;
00725     } else {
00726       tm.tv_sec = 0;
00727       tm.tv_nsec = SPIN_SLEEP_DURATION;
00728       nanosleep(&tm, NULL);
00729       cnt = 0;
00730     }
00731   }
00732 }