linuxthreads/spinlock.c

   1 /* Linuxthreads - a simple clone()-based implementation of Posix        */
   2 /* threads for Linux.                                                   */
   3 /* Copyright (C) 1998 Xavier Leroy (Xavier.Leroy@inria.fr)              */
   4 /*                                                                      */
   5 /* This program is free software; you can redistribute it and/or        */
   6 /* modify it under the terms of the GNU Library General Public License  */
   7 /* as published by the Free Software Foundation; either version 2       */
   8 /* of the License, or (at your option) any later version.               */
   9 /*                                                                      */
  10 /* This program is distributed in the hope that it will be useful,      */
  11 /* but WITHOUT ANY WARRANTY; without even the implied warranty of       */
  12 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the        */
  13 /* GNU Library General Public License for more details.                 */
  14
  15 /* Internal locks */
  16
  17 #include <errno.h>
  18 #include <sched.h>
  19 #include <time.h>
  20 #include <stdlib.h>
  21 #include <limits.h>
  22 #include "pthread.h"
  23 #include "internals.h"
  24 #include "spinlock.h"
  25 #include "restart.h"
  26
  27 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
  28 static void __pthread_acquire(int * spinlock);
  29 #endif
  30
  31
  32 /* The status field of a spinlock is a pointer whose least significant
  33    bit is a locked flag.
  34
  35    Thus the field values have the following meanings:
  36
  37    status == 0:       spinlock is free
  38    status == 1:       spinlock is taken; no thread is waiting on it
  39
  40    (status & 1) == 1: spinlock is taken and (status & ~1L) is a
  41                       pointer to the first waiting thread; other
  42                       waiting threads are linked via the p_nextlock
  43                       field.
  44    (status & 1) == 0: same as above, but spinlock is not taken.
  45
  46    The waiting list is not sorted by priority order.
  47    Actually, we always insert at top of list (sole insertion mode
  48    that can be performed without locking).
  49    For __pthread_unlock, we perform a linear search in the list
  50    to find the highest-priority, oldest waiting thread.
  51    This is safe because there are no concurrent __pthread_unlock
  52    operations -- only the thread that locked the mutex can unlock it. */
  53
  54
  55 void internal_function __pthread_lock(struct _pthread_fastlock * lock,
  56                                       pthread_descr self)
  57 {
  58 #if defined HAS_COMPARE_AND_SWAP
  59   long oldstatus, newstatus;
  60   int successful_seizure, spurious_wakeup_count = 0;
  61   int spin_count = 0;
  62 #endif
  63
  64 #if defined TEST_FOR_COMPARE_AND_SWAP
  65   if (!__pthread_has_cas)
  66 #endif
  67 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
  68   {
  69     __pthread_acquire(&lock->__spinlock);
  70     return;
  71   }
  72 #endif
  73
  74 #if defined HAS_COMPARE_AND_SWAP
  75 again:
  76
  77   /* On SMP, try spinning to get the lock. */
  78
  79   if (__pthread_smp_kernel) {
  80     int max_count = lock->__spinlock * 2 + 10;
  81
  82     for (spin_count = 0; spin_count < max_count; spin_count++) {
  83       if (((oldstatus = lock->__status) & 1) == 0) {
  84         if(__compare_and_swap(&lock->__status, oldstatus, oldstatus | 1))
  85         {
  86           if (spin_count)
  87             lock->__spinlock += (spin_count - lock->__spinlock) / 8;
  88           return;
  89         }
  90       }
  91     }
  92
  93     lock->__spinlock += (spin_count - lock->__spinlock) / 8;
  94   }
  95
  96   /* No luck, try once more or suspend. */
  97
  98   do {
  99     oldstatus = lock->__status;
 100     successful_seizure = 0;
 101
 102     if ((oldstatus & 1) == 0) {
 103       newstatus = oldstatus | 1;
 104       successful_seizure = 1;
 105     } else {
 106       if (self == NULL)
 107         self = thread_self();
 108       newstatus = (long) self | 1;
 109     }
 110
 111     if (self != NULL) {
 112       THREAD_SETMEM(self, p_nextlock, (pthread_descr) (oldstatus & ~1L));
 113       /* Make sure the store in p_nextlock completes before performing
 114          the compare-and-swap */
 115       MEMORY_BARRIER();
 116     }
 117   } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
 118
 119   /* Suspend with guard against spurious wakeup.
 120      This can happen in pthread_cond_timedwait_relative, when the thread
 121      wakes up due to timeout and is still on the condvar queue, and then
 122      locks the queue to remove itself. At that point it may still be on the
 123      queue, and may be resumed by a condition signal. */
 124
 125   if (!successful_seizure) {
 126     for (;;) {
 127       suspend(self);
 128       if (self->p_nextlock != NULL) {
 129         /* Count resumes that don't belong to us. */
 130         spurious_wakeup_count++;
 131         continue;
 132       }
 133       break;
 134     }
 135     goto again;
 136   }
 137
 138   /* Put back any resumes we caught that don't belong to us. */
 139   while (spurious_wakeup_count--)
 140     restart(self);
 141 #endif
 142 }
 143
 144 int __pthread_unlock(struct _pthread_fastlock * lock)
 145 {
 146 #if defined HAS_COMPARE_AND_SWAP
 147   long oldstatus;
 148   pthread_descr thr, * ptr, * maxptr;
 149   int maxprio;
 150 #endif
 151
 152 #if defined TEST_FOR_COMPARE_AND_SWAP
 153   if (!__pthread_has_cas)
 154 #endif
 155 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 156   {
 157     WRITE_MEMORY_BARRIER();
 158     lock->__spinlock = 0;
 159     return 0;
 160   }
 161 #endif
 162
 163 #if defined HAS_COMPARE_AND_SWAP
 164 again:
 165   oldstatus = lock->__status;
 166
 167   while ((oldstatus = lock->__status) == 1) {
 168     if (__compare_and_swap_with_release_semantics(&lock->__status,
 169         oldstatus, 0))
 170       return 0;
 171   }
 172
 173   /* Find thread in waiting queue with maximal priority */
 174   ptr = (pthread_descr *) &lock->__status;
 175   thr = (pthread_descr) (oldstatus & ~1L);
 176   maxprio = 0;
 177   maxptr = ptr;
 178   while (thr != 0) {
 179     if (thr->p_priority >= maxprio) {
 180       maxptr = ptr;
 181       maxprio = thr->p_priority;
 182     }
 183     ptr = &(thr->p_nextlock);
 184     /* Prevent reordering of the load of lock->__status above and the
 185        load of *ptr below, as well as reordering of *ptr between
 186        several iterations of the while loop.  Some processors (e.g.
 187        multiprocessor Alphas) could perform such reordering even though
 188        the loads are dependent. */
 189     READ_MEMORY_BARRIER();
 190     thr = *ptr;
 191   }
 192   /* Prevent reordering of the load of lock->__status above and
 193      thr->p_nextlock below */
 194   READ_MEMORY_BARRIER();
 195   /* Remove max prio thread from waiting list. */
 196   if (maxptr == (pthread_descr *) &lock->__status) {
 197     /* If max prio thread is at head, remove it with compare-and-swap
 198        to guard against concurrent lock operation. This removal
 199        also has the side effect of marking the lock as released
 200        because the new status comes from thr->p_nextlock whose
 201        least significant bit is clear. */
 202     thr = (pthread_descr) (oldstatus & ~1L);
 203     if (! __compare_and_swap_with_release_semantics
 204             (&lock->__status, oldstatus, (long)(thr->p_nextlock)))
 205       goto again;
 206   } else {
 207     /* No risk of concurrent access, remove max prio thread normally.
 208        But in this case we must also flip the least significant bit
 209        of the status to mark the lock as released. */
 210     thr = *maxptr;
 211     *maxptr = thr->p_nextlock;
 212
 213     do {
 214       oldstatus = lock->__status;
 215     } while (!__compare_and_swap_with_release_semantics(&lock->__status,
 216              oldstatus, oldstatus & ~1L));
 217   }
 218   /* Prevent reordering of store to *maxptr above and store to thr->p_nextlock
 219      below */
 220   WRITE_MEMORY_BARRIER();
 221   /* Wake up the selected waiting thread */
 222   thr->p_nextlock = NULL;
 223   restart(thr);
 224
 225   return 0;
 226 #endif
 227 }
 228
 229 /*
 230  * Alternate fastlocks do not queue threads directly. Instead, they queue
 231  * these wait queue node structures. When a timed wait wakes up due to
 232  * a timeout, it can leave its wait node in the queue (because there
 233  * is no safe way to remove from the quue). Some other thread will
 234  * deallocate the abandoned node.
 235  */
 236
 237
 238 struct wait_node {
 239   struct wait_node *next;       /* Next node in null terminated linked list */
 240   pthread_descr thr;            /* The thread waiting with this node */
 241   int abandoned;                /* Atomic flag */
 242 };
 243
 244 static long wait_node_free_list;
 245 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 246 static int wait_node_free_list_spinlock;
 247 #endif
 248
 249 /* Allocate a new node from the head of the free list using an atomic
 250    operation, or else using malloc if that list is empty.  A fundamental
 251    assumption here is that we can safely access wait_node_free_list->next.
 252    That's because we never free nodes once we allocate them, so a pointer to a
 253    node remains valid indefinitely. */
 254
 255 static struct wait_node *wait_node_alloc(void)
 256 {
 257 #if defined HAS_COMPARE_AND_SWAP
 258   long oldvalue, newvalue;
 259 #endif
 260
 261 #if defined TEST_FOR_COMPARE_AND_SWAP
 262   if (!__pthread_has_cas)
 263 #endif
 264 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 265   {
 266     struct wait_node *new_node = 0;
 267
 268     __pthread_acquire(&wait_node_free_list_spinlock);
 269     if (wait_node_free_list != 0) {
 270       new_node = (struct wait_node *) wait_node_free_list;
 271       wait_node_free_list = (long) new_node->next;
 272     }
 273     WRITE_MEMORY_BARRIER();
 274     wait_node_free_list_spinlock = 0;
 275
 276     if (new_node == 0)
 277       return malloc(sizeof *wait_node_alloc());
 278
 279     return new_node;
 280   }
 281 #endif
 282
 283 #if defined HAS_COMPARE_AND_SWAP
 284   do {
 285     oldvalue = wait_node_free_list;
 286
 287     if (oldvalue == 0)
 288       return malloc(sizeof *wait_node_alloc());
 289
 290     newvalue = (long) ((struct wait_node *) oldvalue)->next;
 291     WRITE_MEMORY_BARRIER();
 292   } while (! __compare_and_swap(&wait_node_free_list, oldvalue, newvalue));
 293
 294   return (struct wait_node *) oldvalue;
 295 #endif
 296 }
 297
 298 /* Return a node to the head of the free list using an atomic
 299    operation. */
 300
 301 static void wait_node_free(struct wait_node *wn)
 302 {
 303 #if defined HAS_COMPARE_AND_SWAP
 304   long oldvalue, newvalue;
 305 #endif
 306
 307 #if defined TEST_FOR_COMPARE_AND_SWAP
 308   if (!__pthread_has_cas)
 309 #endif
 310 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 311   {
 312     __pthread_acquire(&wait_node_free_list_spinlock);
 313     wn->next = (struct wait_node *) wait_node_free_list;
 314     wait_node_free_list = (long) wn;
 315     WRITE_MEMORY_BARRIER();
 316     wait_node_free_list_spinlock = 0;
 317     return;
 318   }
 319 #endif
 320
 321 #if defined HAS_COMPARE_AND_SWAP
 322   do {
 323     oldvalue = wait_node_free_list;
 324     wn->next = (struct wait_node *) oldvalue;
 325     newvalue = (long) wn;
 326     WRITE_MEMORY_BARRIER();
 327   } while (! __compare_and_swap(&wait_node_free_list, oldvalue, newvalue));
 328 #endif
 329 }
 330
 331 #if defined HAS_COMPARE_AND_SWAP
 332
 333 /* Remove a wait node from the specified queue.  It is assumed
 334    that the removal takes place concurrently with only atomic insertions at the
 335    head of the queue. */
 336
 337 static void wait_node_dequeue(struct wait_node **pp_head,
 338                               struct wait_node **pp_node,
 339                               struct wait_node *p_node)
 340 {
 341   /* If the node is being deleted from the head of the
 342      list, it must be deleted using atomic compare-and-swap.
 343      Otherwise it can be deleted in the straightforward way. */
 344
 345   if (pp_node == pp_head) {
 346     long oldvalue = (long) p_node;
 347     long newvalue = (long) p_node->next;
 348
 349     if (__compare_and_swap((long *) pp_node, oldvalue, newvalue))
 350       return;
 351
 352     /* Oops! Compare and swap failed, which means the node is
 353        no longer first. We delete it using the ordinary method.  But we don't
 354        know the identity of the node which now holds the pointer to the node
 355        being deleted, so we must search from the beginning. */
 356
 357     for (pp_node = pp_head; *pp_node != p_node; pp_node = &(*pp_node)->next)
 358       ; /* null body */
 359   }
 360
 361   *pp_node = p_node->next;
 362   return;
 363 }
 364
 365 #endif
 366
 367 void __pthread_alt_lock(struct _pthread_fastlock * lock,
 368                         pthread_descr self)
 369 {
 370 #if defined HAS_COMPARE_AND_SWAP
 371   long oldstatus, newstatus;
 372 #endif
 373   struct wait_node wait_node;
 374
 375 #if defined TEST_FOR_COMPARE_AND_SWAP
 376   if (!__pthread_has_cas)
 377 #endif
 378 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 379   {
 380     int suspend_needed = 0;
 381     __pthread_acquire(&lock->__spinlock);
 382
 383     if (lock->__status == 0)
 384       lock->__status = 1;
 385     else {
 386       if (self == NULL)
 387         self = thread_self();
 388
 389       wait_node.abandoned = 0;
 390       wait_node.next = (struct wait_node *) lock->__status;
 391       wait_node.thr = self;
 392       lock->__status = (long) &wait_node;
 393       suspend_needed = 1;
 394     }
 395
 396     WRITE_MEMORY_BARRIER();
 397     lock->__spinlock = 0;
 398
 399     if (suspend_needed)
 400       suspend (self);
 401     return;
 402   }
 403 #endif
 404
 405 #if defined HAS_COMPARE_AND_SWAP
 406   do {
 407     oldstatus = lock->__status;
 408     if (oldstatus == 0) {
 409       newstatus = 1;
 410     } else {
 411       if (self == NULL)
 412         self = thread_self();
 413       wait_node.thr = self;
 414       newstatus = (long) &wait_node;
 415     }
 416     wait_node.abandoned = 0;
 417     wait_node.next = (struct wait_node *) oldstatus;
 418     /* Make sure the store in wait_node.next completes before performing
 419        the compare-and-swap */
 420     MEMORY_BARRIER();
 421   } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
 422
 423   /* Suspend. Note that unlike in __pthread_lock, we don't worry
 424      here about spurious wakeup. That's because this lock is not
 425      used in situations where that can happen; the restart can
 426      only come from the previous lock owner. */
 427
 428   if (oldstatus != 0)
 429     suspend(self);
 430 #endif
 431 }
 432
 433 /* Timed-out lock operation; returns 0 to indicate timeout. */
 434
 435 int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
 436                             pthread_descr self, const struct timespec *abstime)
 437 {
 438   long oldstatus = 0;
 439 #if defined HAS_COMPARE_AND_SWAP
 440   long newstatus;
 441 #endif
 442   struct wait_node *p_wait_node = wait_node_alloc();
 443
 444   /* Out of memory, just give up and do ordinary lock. */
 445   if (p_wait_node == 0) {
 446     __pthread_alt_lock(lock, self);
 447     return 1;
 448   }
 449
 450 #if defined TEST_FOR_COMPARE_AND_SWAP
 451   if (!__pthread_has_cas)
 452 #endif
 453 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 454   {
 455     __pthread_acquire(&lock->__spinlock);
 456
 457     if (lock->__status == 0)
 458       lock->__status = 1;
 459     else {
 460       if (self == NULL)
 461         self = thread_self();
 462
 463       p_wait_node->abandoned = 0;
 464       p_wait_node->next = (struct wait_node *) lock->__status;
 465       p_wait_node->thr = self;
 466       lock->__status = (long) p_wait_node;
 467       oldstatus = 1; /* force suspend */
 468     }
 469
 470     WRITE_MEMORY_BARRIER();
 471     lock->__spinlock = 0;
 472     goto suspend;
 473   }
 474 #endif
 475
 476 #if defined HAS_COMPARE_AND_SWAP
 477   do {
 478     oldstatus = lock->__status;
 479     if (oldstatus == 0) {
 480       newstatus = 1;
 481     } else {
 482       if (self == NULL)
 483         self = thread_self();
 484       p_wait_node->thr = self;
 485       newstatus = (long) p_wait_node;
 486     }
 487     p_wait_node->abandoned = 0;
 488     p_wait_node->next = (struct wait_node *) oldstatus;
 489     /* Make sure the store in wait_node.next completes before performing
 490        the compare-and-swap */
 491     MEMORY_BARRIER();
 492   } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
 493 #endif
 494
 495 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 496   suspend:
 497 #endif
 498
 499   /* If we did not get the lock, do a timed suspend. If we wake up due
 500      to a timeout, then there is a race; the old lock owner may try
 501      to remove us from the queue. This race is resolved by us and the owner
 502      doing an atomic testandset() to change the state of the wait node from 0
 503      to 1. If we succeed, then it's a timeout and we abandon the node in the
 504      queue. If we fail, it means the owner gave us the lock. */
 505
 506   if (oldstatus != 0) {
 507     if (timedsuspend(self, abstime) == 0) {
 508       if (!testandset(&p_wait_node->abandoned))
 509         return 0; /* Timeout! */
 510
 511       /* Eat oustanding resume from owner, otherwise wait_node_free() below
 512          will race with owner's wait_node_dequeue(). */
 513       suspend(self);
 514     }
 515   }
 516
 517   wait_node_free(p_wait_node);
 518
 519   return 1; /* Got the lock! */
 520 }
 521
 522 void __pthread_alt_unlock(struct _pthread_fastlock *lock)
 523 {
 524   struct wait_node *p_node, **pp_node, *p_max_prio, **pp_max_prio;
 525   struct wait_node ** const pp_head = (struct wait_node **) &lock->__status;
 526   int maxprio;
 527
 528 #if defined TEST_FOR_COMPARE_AND_SWAP
 529   if (!__pthread_has_cas)
 530 #endif
 531 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 532   {
 533     __pthread_acquire(&lock->__spinlock);
 534   }
 535 #endif
 536
 537   while (1) {
 538
 539   /* If no threads are waiting for this lock, try to just
 540      atomically release it. */
 541 #if defined TEST_FOR_COMPARE_AND_SWAP
 542     if (!__pthread_has_cas)
 543 #endif
 544 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 545     {
 546       if (lock->__status == 0 || lock->__status == 1) {
 547         lock->__status = 0;
 548         break;
 549       }
 550     }
 551 #endif
 552
 553 #if defined TEST_FOR_COMPARE_AND_SWAP
 554     else
 555 #endif
 556
 557 #if defined HAS_COMPARE_AND_SWAP
 558     {
 559       long oldstatus = lock->__status;
 560       if (oldstatus == 0 || oldstatus == 1) {
 561         if (__compare_and_swap_with_release_semantics (&lock->__status, oldstatus, 0))
 562           break;
 563         else
 564           continue;
 565       }
 566     }
 567 #endif
 568
 569     /* Process the entire queue of wait nodes. Remove all abandoned
 570        wait nodes and put them into the global free queue, and
 571        remember the one unabandoned node which refers to the thread
 572        having the highest priority. */
 573
 574     pp_max_prio = pp_node = pp_head;
 575     p_max_prio = p_node = *pp_head;
 576     maxprio = INT_MIN;
 577
 578     while (p_node != (struct wait_node *) 1) {
 579       int prio;
 580
 581       if (p_node->abandoned) {
 582         /* Remove abandoned node. */
 583 #if defined TEST_FOR_COMPARE_AND_SWAP
 584         if (!__pthread_has_cas)
 585 #endif
 586 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 587           *pp_node = p_node->next;
 588 #endif
 589 #if defined TEST_FOR_COMPARE_AND_SWAP
 590         else
 591 #endif
 592 #if defined HAS_COMPARE_AND_SWAP
 593           wait_node_dequeue(pp_head, pp_node, p_node);
 594 #endif
 595         wait_node_free(p_node);
 596         READ_MEMORY_BARRIER();
 597         p_node = *pp_node;
 598         continue;
 599       } else if ((prio = p_node->thr->p_priority) >= maxprio) {
 600         /* Otherwise remember it if its thread has a higher or equal priority
 601            compared to that of any node seen thus far. */
 602         maxprio = prio;
 603         pp_max_prio = pp_node;
 604         p_max_prio = p_node;
 605       }
 606
 607       pp_node = &p_node->next;
 608       READ_MEMORY_BARRIER();
 609       p_node = *pp_node;
 610     }
 611
 612     READ_MEMORY_BARRIER();
 613
 614     /* If all threads abandoned, go back to top */
 615     if (maxprio == INT_MIN)
 616       continue;
 617
 618     ASSERT (p_max_prio != (struct wait_node *) 1);
 619
 620     /* Now we want to to remove the max priority thread's wait node from
 621        the list. Before we can do this, we must atomically try to change the
 622        node's abandon state from zero to nonzero. If we succeed, that means we
 623        have the node that we will wake up. If we failed, then it means the
 624        thread timed out and abandoned the node in which case we repeat the
 625        whole unlock operation. */
 626
 627     if (!testandset(&p_max_prio->abandoned)) {
 628 #if defined TEST_FOR_COMPARE_AND_SWAP
 629       if (!__pthread_has_cas)
 630 #endif
 631 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 632         *pp_max_prio = p_max_prio->next;
 633 #endif
 634 #if defined TEST_FOR_COMPARE_AND_SWAP
 635       else
 636 #endif
 637 #if defined HAS_COMPARE_AND_SWAP
 638         wait_node_dequeue(pp_head, pp_max_prio, p_max_prio);
 639 #endif
 640       WRITE_MEMORY_BARRIER();
 641       restart(p_max_prio->thr);
 642       break;
 643     }
 644   }
 645
 646 #if defined TEST_FOR_COMPARE_AND_SWAP
 647   if (!__pthread_has_cas)
 648 #endif
 649 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 650   {
 651     WRITE_MEMORY_BARRIER();
 652     lock->__spinlock = 0;
 653   }
 654 #endif
 655 }
 656
 657
 658 /* Compare-and-swap emulation with a spinlock */
 659
 660 #ifdef TEST_FOR_COMPARE_AND_SWAP
 661 int __pthread_has_cas = 0;
 662 #endif
 663
 664 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 665
 666 int __pthread_compare_and_swap(long * ptr, long oldval, long newval,
 667                                int * spinlock)
 668 {
 669   int res;
 670   if (testandset(spinlock)) __pthread_acquire(spinlock);
 671   if (*ptr == oldval) {
 672     *ptr = newval; res = 1;
 673   } else {
 674     res = 0;
 675   }
 676   /* Prevent reordering of store to *ptr above and store to *spinlock below */
 677   WRITE_MEMORY_BARRIER();
 678   *spinlock = 0;
 679   return res;
 680 }
 681
 682 /* This function is called if the inlined test-and-set
 683    in __pthread_compare_and_swap() failed */
 684
 685 /* The retry strategy is as follows:
 686    - We test and set the spinlock MAX_SPIN_COUNT times, calling
 687      sched_yield() each time.  This gives ample opportunity for other
 688      threads with priority >= our priority to make progress and
 689      release the spinlock.
 690    - If a thread with priority < our priority owns the spinlock,
 691      calling sched_yield() repeatedly is useless, since we're preventing
 692      the owning thread from making progress and releasing the spinlock.
 693      So, after MAX_SPIN_LOCK attemps, we suspend the calling thread
 694      using nanosleep().  This again should give time to the owning thread
 695      for releasing the spinlock.
 696      Notice that the nanosleep() interval must not be too small,
 697      since the kernel does busy-waiting for short intervals in a realtime
 698      process (!).  The smallest duration that guarantees thread
 699      suspension is currently 2ms.
 700    - When nanosleep() returns, we try again, doing MAX_SPIN_COUNT
 701      sched_yield(), then sleeping again if needed. */
 702
 703 static void __pthread_acquire(int * spinlock)
 704 {
 705   int cnt = 0;
 706   struct timespec tm;
 707
 708   while (testandset(spinlock)) {
 709     if (cnt < MAX_SPIN_COUNT) {
 710       sched_yield();
 711       cnt++;
 712     } else {
 713       tm.tv_sec = 0;
 714       tm.tv_nsec = SPIN_SLEEP_DURATION;
 715       nanosleep(&tm, NULL);
 716       cnt = 0;
 717     }
 718   }
 719 }
 720
 721 #endif