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