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