1 /* Linuxthreads - a simple clone()-based implementation of Posix */
2 /* threads for Linux. */
3 /* Copyright (C) 1998 Xavier Leroy (Xavier.Leroy@inria.fr) */
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. */
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. */
23 #include "internals.h"
27 libpthread_hidden_proto(nanosleep
)
29 static void __pthread_acquire(int * spinlock
);
31 static __inline__
void __pthread_release(int * spinlock
)
33 WRITE_MEMORY_BARRIER();
34 *spinlock
= __LT_SPINLOCK_INIT
;
35 __asm__
__volatile__ ("" : "=m" (*spinlock
) : "m" (*spinlock
));
39 /* The status field of a spinlock is a pointer whose least significant
42 Thus the field values have the following meanings:
44 status == 0: spinlock is free
45 status == 1: spinlock is taken; no thread is waiting on it
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
51 (status & 1) == 0: same as above, but spinlock is not taken.
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. */
62 void internal_function
__pthread_lock(struct _pthread_fastlock
* lock
,
65 #if defined HAS_COMPARE_AND_SWAP
66 long oldstatus
, newstatus
;
67 int successful_seizure
, spurious_wakeup_count
;
70 #if defined TEST_FOR_COMPARE_AND_SWAP
71 if (!__pthread_has_cas
)
73 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
75 __pthread_acquire(&lock
->__spinlock
);
80 #if defined HAS_COMPARE_AND_SWAP
81 /* First try it without preparation. Maybe it's a completely
83 if (lock
->__status
== 0 && __compare_and_swap (&lock
->__status
, 0, 1))
86 spurious_wakeup_count
= 0;
88 /* On SMP, try spinning to get the lock. */
90 if (__pthread_smp_kernel
) {
92 int max_count
= lock
->__spinlock
* 2 + 10;
94 if (max_count
> MAX_ADAPTIVE_SPIN_COUNT
)
95 max_count
= MAX_ADAPTIVE_SPIN_COUNT
;
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))
102 lock
->__spinlock
+= (spin_count
- lock
->__spinlock
) / 8;
103 READ_MEMORY_BARRIER();
110 __asm__
__volatile__ ("" : "=m" (lock
->__status
) : "m" (lock
->__status
));
113 lock
->__spinlock
+= (spin_count
- lock
->__spinlock
) / 8;
119 /* No luck, try once more or suspend. */
122 oldstatus
= lock
->__status
;
123 successful_seizure
= 0;
125 if ((oldstatus
& 1) == 0) {
126 newstatus
= oldstatus
| 1;
127 successful_seizure
= 1;
130 self
= thread_self();
131 newstatus
= (long) self
| 1;
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 */
140 } while(! __compare_and_swap(&lock
->__status
, oldstatus
, newstatus
));
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. */
148 if (!successful_seizure
) {
151 if (self
->p_nextlock
!= NULL
) {
152 /* Count resumes that don't belong to us. */
153 spurious_wakeup_count
++;
161 /* Put back any resumes we caught that don't belong to us. */
162 while (spurious_wakeup_count
--)
165 READ_MEMORY_BARRIER();
169 int __pthread_unlock(struct _pthread_fastlock
* lock
)
171 #if defined HAS_COMPARE_AND_SWAP
173 pthread_descr thr
, * ptr
, * maxptr
;
177 #if defined TEST_FOR_COMPARE_AND_SWAP
178 if (!__pthread_has_cas
)
180 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
182 __pthread_release(&lock
->__spinlock
);
187 #if defined HAS_COMPARE_AND_SWAP
188 WRITE_MEMORY_BARRIER();
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
,
203 /* Find thread in waiting queue with maximal priority */
204 ptr
= (pthread_descr
*) &lock
->__status
;
205 thr
= (pthread_descr
) (oldstatus
& ~1L);
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. */
217 READ_MEMORY_BARRIER();
220 if (thr
->p_priority
>= maxprio
) {
222 maxprio
= thr
->p_priority
;
224 ptr
= &(thr
->p_nextlock
);
225 thr
= (pthread_descr
)((long)(thr
->p_nextlock
) & ~1L);
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))
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
;
246 /* Ensure deletion from linked list completes before we
248 WRITE_MEMORY_BARRIER();
251 oldstatus
= lock
->__status
;
252 } while (!__compare_and_swap_with_release_semantics(&lock
->__status
,
253 oldstatus
, oldstatus
& ~1L));
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. */
261 thr
->p_nextlock
= NULL
;
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.
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 */
283 static long wait_node_free_list
;
284 static int wait_node_free_list_spinlock
;
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. */
292 static struct wait_node
*wait_node_alloc(void)
294 struct wait_node
*new_node
= 0;
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
;
301 WRITE_MEMORY_BARRIER();
302 __pthread_release(&wait_node_free_list_spinlock
);
305 return malloc(sizeof *wait_node_alloc());
310 /* Return a node to the head of the free list using an atomic
313 static void wait_node_free(struct wait_node
*wn
)
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
);
323 #if defined HAS_COMPARE_AND_SWAP
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. */
329 static void wait_node_dequeue(struct wait_node
**pp_head
,
330 struct wait_node
**pp_node
,
331 struct wait_node
*p_node
)
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. */
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. */
342 long oldvalue
= (long) p_node
;
343 long newvalue
= (long) p_node
->next
;
345 if (__compare_and_swap((long *) pp_node
, oldvalue
, newvalue
))
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. */
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. */
359 *pp_node
= p_node
->next
;
365 void __pthread_alt_lock(struct _pthread_fastlock
* lock
,
368 #if defined HAS_COMPARE_AND_SWAP
369 long oldstatus
, newstatus
;
371 struct wait_node wait_node
;
373 #if defined TEST_FOR_COMPARE_AND_SWAP
374 if (!__pthread_has_cas
)
376 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
378 int suspend_needed
= 0;
379 __pthread_acquire(&lock
->__spinlock
);
381 if (lock
->__status
== 0)
385 self
= thread_self();
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
;
394 __pthread_release(&lock
->__spinlock
);
402 #if defined HAS_COMPARE_AND_SWAP
404 oldstatus
= lock
->__status
;
405 if (oldstatus
== 0) {
409 self
= thread_self();
410 wait_node
.thr
= self
;
411 newstatus
= (long) &wait_node
;
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 */
418 } while(! __compare_and_swap(&lock
->__status
, oldstatus
, newstatus
));
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. */
428 READ_MEMORY_BARRIER();
432 /* Timed-out lock operation; returns 0 to indicate timeout. */
434 int __pthread_alt_timedlock(struct _pthread_fastlock
* lock
,
435 pthread_descr self
, const struct timespec
*abstime
)
438 #if defined HAS_COMPARE_AND_SWAP
441 struct wait_node
*p_wait_node
= wait_node_alloc();
443 /* Out of memory, just give up and do ordinary lock. */
444 if (p_wait_node
== 0) {
445 __pthread_alt_lock(lock
, self
);
449 #if defined TEST_FOR_COMPARE_AND_SWAP
450 if (!__pthread_has_cas
)
452 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
454 __pthread_acquire(&lock
->__spinlock
);
456 if (lock
->__status
== 0)
460 self
= thread_self();
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 */
469 __pthread_release(&lock
->__spinlock
);
474 #if defined HAS_COMPARE_AND_SWAP
476 oldstatus
= lock
->__status
;
477 if (oldstatus
== 0) {
481 self
= thread_self();
482 p_wait_node
->thr
= self
;
483 newstatus
= (long) p_wait_node
;
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 */
490 } while(! __compare_and_swap(&lock
->__status
, oldstatus
, newstatus
));
493 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
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. */
504 if (oldstatus
!= 0) {
505 if (timedsuspend(self
, abstime
) == 0) {
506 if (!testandset(&p_wait_node
->abandoned
))
507 return 0; /* Timeout! */
509 /* Eat oustanding resume from owner, otherwise wait_node_free() below
510 will race with owner's wait_node_dequeue(). */
515 wait_node_free(p_wait_node
);
517 READ_MEMORY_BARRIER();
519 return 1; /* Got the lock! */
522 void __pthread_alt_unlock(struct _pthread_fastlock
*lock
)
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
;
528 WRITE_MEMORY_BARRIER();
530 #if defined TEST_FOR_COMPARE_AND_SWAP
531 if (!__pthread_has_cas
)
533 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
535 __pthread_acquire(&lock
->__spinlock
);
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
)
546 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
548 if (lock
->__status
== 0 || lock
->__status
== 1) {
555 #if defined TEST_FOR_COMPARE_AND_SWAP
559 #if defined HAS_COMPARE_AND_SWAP
561 long oldstatus
= lock
->__status
;
562 if (oldstatus
== 0 || oldstatus
== 1) {
563 if (__compare_and_swap_with_release_semantics (&lock
->__status
, oldstatus
, 0))
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. */
576 pp_max_prio
= pp_node
= pp_head
;
577 p_max_prio
= p_node
= *pp_head
;
580 READ_MEMORY_BARRIER(); /* Prevent access to stale data through p_node */
582 while (p_node
!= (struct wait_node
*) 1) {
585 if (p_node
->abandoned
) {
586 /* Remove abandoned node. */
587 #if defined TEST_FOR_COMPARE_AND_SWAP
588 if (!__pthread_has_cas
)
590 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
591 *pp_node
= p_node
->next
;
593 #if defined TEST_FOR_COMPARE_AND_SWAP
596 #if defined HAS_COMPARE_AND_SWAP
597 wait_node_dequeue(pp_head
, pp_node
, p_node
);
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
605 if (pp_node
== pp_head
)
606 READ_MEMORY_BARRIER(); /* No stale reads through p_node */
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. */
612 pp_max_prio
= pp_node
;
616 /* This canno6 jump backward in the list, so no further read
617 barrier is needed. */
618 pp_node
= &p_node
->next
;
622 /* If all threads abandoned, go back to top */
623 if (maxprio
== INT_MIN
)
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. */
633 if (!testandset(&p_max_prio
->abandoned
)) {
634 #if defined TEST_FOR_COMPARE_AND_SWAP
635 if (!__pthread_has_cas
)
637 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
638 *pp_max_prio
= p_max_prio
->next
;
640 #if defined TEST_FOR_COMPARE_AND_SWAP
643 #if defined HAS_COMPARE_AND_SWAP
644 wait_node_dequeue(pp_head
, pp_max_prio
, p_max_prio
);
646 restart(p_max_prio
->thr
);
651 #if defined TEST_FOR_COMPARE_AND_SWAP
652 if (!__pthread_has_cas
)
654 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
656 __pthread_release(&lock
->__spinlock
);
662 /* Compare-and-swap emulation with a spinlock */
664 #ifdef TEST_FOR_COMPARE_AND_SWAP
665 int __pthread_has_cas
= 0;
668 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
670 int __pthread_compare_and_swap(long * ptr
, long oldval
, long newval
,
675 __pthread_acquire(spinlock
);
677 if (*ptr
== oldval
) {
678 *ptr
= newval
; res
= 1;
683 __pthread_release(spinlock
);
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. */
708 static void __pthread_acquire(int * spinlock
)
713 READ_MEMORY_BARRIER();
715 while (testandset(spinlock
)) {
716 if (cnt
< MAX_SPIN_COUNT
) {
721 tm
.tv_nsec
= SPIN_SLEEP_DURATION
;
722 nanosleep(&tm
, NULL
);