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 static void __pthread_acquire(int * spinlock);
29 static inline void __pthread_release(int * spinlock)
31 WRITE_MEMORY_BARRIER();
32 *spinlock = __LT_SPINLOCK_INIT;
33 __asm __volatile ("" : "=m" (*spinlock) : "0" (*spinlock));
37 /* The status field of a spinlock is a pointer whose least significant
40 Thus the field values have the following meanings:
42 status == 0: spinlock is free
43 status == 1: spinlock is taken; no thread is waiting on it
45 (status & 1) == 1: spinlock is taken and (status & ~1L) is a
46 pointer to the first waiting thread; other
47 waiting threads are linked via the p_nextlock
49 (status & 1) == 0: same as above, but spinlock is not taken.
51 The waiting list is not sorted by priority order.
52 Actually, we always insert at top of list (sole insertion mode
53 that can be performed without locking).
54 For __pthread_unlock, we perform a linear search in the list
55 to find the highest-priority, oldest waiting thread.
56 This is safe because there are no concurrent __pthread_unlock
57 operations -- only the thread that locked the mutex can unlock it. */
60 void internal_function __pthread_lock(struct _pthread_fastlock * lock,
63 #if defined HAS_COMPARE_AND_SWAP
64 long oldstatus, newstatus;
65 int successful_seizure, spurious_wakeup_count;
69 #if defined TEST_FOR_COMPARE_AND_SWAP
70 if (!__pthread_has_cas)
72 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
74 __pthread_acquire(&lock->__spinlock);
79 #if defined HAS_COMPARE_AND_SWAP
80 /* First try it without preparation. Maybe it's a completely
82 if (lock->__status == 0 && __compare_and_swap (&lock->__status, 0, 1))
85 spurious_wakeup_count = 0;
88 /* On SMP, try spinning to get the lock. */
90 if (__pthread_smp_kernel) {
91 int max_count = lock->__spinlock * 2 + 10;
93 if (max_count > MAX_ADAPTIVE_SPIN_COUNT)
94 max_count = MAX_ADAPTIVE_SPIN_COUNT;
96 for (spin_count = 0; spin_count < max_count; spin_count++) {
97 if (((oldstatus = lock->__status) & 1) == 0) {
98 if(__compare_and_swap(&lock->__status, oldstatus, oldstatus | 1))
101 lock->__spinlock += (spin_count - lock->__spinlock) / 8;
102 READ_MEMORY_BARRIER();
109 __asm __volatile ("" : "=m" (lock->__status) : "0" (lock->__status));
112 lock->__spinlock += (spin_count - lock->__spinlock) / 8;
117 /* No luck, try once more or suspend. */
120 oldstatus = lock->__status;
121 successful_seizure = 0;
123 if ((oldstatus & 1) == 0) {
124 newstatus = oldstatus | 1;
125 successful_seizure = 1;
128 self = thread_self();
129 newstatus = (long) self | 1;
133 THREAD_SETMEM(self, p_nextlock, (pthread_descr) (oldstatus));
134 /* Make sure the store in p_nextlock completes before performing
135 the compare-and-swap */
138 } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
140 /* Suspend with guard against spurious wakeup.
141 This can happen in pthread_cond_timedwait_relative, when the thread
142 wakes up due to timeout and is still on the condvar queue, and then
143 locks the queue to remove itself. At that point it may still be on the
144 queue, and may be resumed by a condition signal. */
146 if (!successful_seizure) {
149 if (self->p_nextlock != NULL) {
150 /* Count resumes that don't belong to us. */
151 spurious_wakeup_count++;
159 /* Put back any resumes we caught that don't belong to us. */
160 while (spurious_wakeup_count--)
163 READ_MEMORY_BARRIER();
167 int __pthread_unlock(struct _pthread_fastlock * lock)
169 #if defined HAS_COMPARE_AND_SWAP
171 pthread_descr thr, * ptr, * maxptr;
175 #if defined TEST_FOR_COMPARE_AND_SWAP
176 if (!__pthread_has_cas)
178 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
180 __pthread_release(&lock->__spinlock);
185 #if defined HAS_COMPARE_AND_SWAP
186 WRITE_MEMORY_BARRIER();
189 while ((oldstatus = lock->__status) == 1) {
190 if (__compare_and_swap_with_release_semantics(&lock->__status,
195 /* Find thread in waiting queue with maximal priority */
196 ptr = (pthread_descr *) &lock->__status;
197 thr = (pthread_descr) (oldstatus & ~1L);
201 /* Before we iterate over the wait queue, we need to execute
202 a read barrier, otherwise we may read stale contents of nodes that may
203 just have been inserted by other processors. One read barrier is enough to
204 ensure we have a stable list; we don't need one for each pointer chase
205 through the list, because we are the owner of the lock; other threads
206 can only add nodes at the front; if a front node is consistent,
207 the ones behind it must also be. */
209 READ_MEMORY_BARRIER();
212 if (thr->p_priority >= maxprio) {
214 maxprio = thr->p_priority;
216 ptr = &(thr->p_nextlock);
217 thr = (pthread_descr)((long)(thr->p_nextlock) & ~1L);
220 /* Remove max prio thread from waiting list. */
221 if (maxptr == (pthread_descr *) &lock->__status) {
222 /* If max prio thread is at head, remove it with compare-and-swap
223 to guard against concurrent lock operation. This removal
224 also has the side effect of marking the lock as released
225 because the new status comes from thr->p_nextlock whose
226 least significant bit is clear. */
227 thr = (pthread_descr) (oldstatus & ~1L);
228 if (! __compare_and_swap_with_release_semantics
229 (&lock->__status, oldstatus, (long)(thr->p_nextlock) & ~1L))
232 /* No risk of concurrent access, remove max prio thread normally.
233 But in this case we must also flip the least significant bit
234 of the status to mark the lock as released. */
235 thr = (pthread_descr)((long)*maxptr & ~1L);
236 *maxptr = thr->p_nextlock;
238 /* Ensure deletion from linked list completes before we
240 WRITE_MEMORY_BARRIER();
243 oldstatus = lock->__status;
244 } while (!__compare_and_swap_with_release_semantics(&lock->__status,
245 oldstatus, oldstatus & ~1L));
248 /* Wake up the selected waiting thread. Woken thread can check
249 its own p_nextlock field for NULL to detect that it has been removed. No
250 barrier is needed here, since restart() and suspend() take
251 care of memory synchronization. */
253 thr->p_nextlock = NULL;
261 * Alternate fastlocks do not queue threads directly. Instead, they queue
262 * these wait queue node structures. When a timed wait wakes up due to
263 * a timeout, it can leave its wait node in the queue (because there
264 * is no safe way to remove from the quue). Some other thread will
265 * deallocate the abandoned node.
270 struct wait_node *next; /* Next node in null terminated linked list */
271 pthread_descr thr; /* The thread waiting with this node */
272 int abandoned; /* Atomic flag */
275 static long wait_node_free_list;
276 static int wait_node_free_list_spinlock;
278 /* Allocate a new node from the head of the free list using an atomic
279 operation, or else using malloc if that list is empty. A fundamental
280 assumption here is that we can safely access wait_node_free_list->next.
281 That's because we never free nodes once we allocate them, so a pointer to a
282 node remains valid indefinitely. */
284 static struct wait_node *wait_node_alloc(void)
286 struct wait_node *new_node = 0;
288 __pthread_acquire(&wait_node_free_list_spinlock);
289 if (wait_node_free_list != 0) {
290 new_node = (struct wait_node *) wait_node_free_list;
291 wait_node_free_list = (long) new_node->next;
293 WRITE_MEMORY_BARRIER();
294 __pthread_release(&wait_node_free_list_spinlock);
297 return malloc(sizeof *wait_node_alloc());
302 /* Return a node to the head of the free list using an atomic
305 static void wait_node_free(struct wait_node *wn)
307 __pthread_acquire(&wait_node_free_list_spinlock);
308 wn->next = (struct wait_node *) wait_node_free_list;
309 wait_node_free_list = (long) wn;
310 WRITE_MEMORY_BARRIER();
311 __pthread_release(&wait_node_free_list_spinlock);
315 #if defined HAS_COMPARE_AND_SWAP
317 /* Remove a wait node from the specified queue. It is assumed
318 that the removal takes place concurrently with only atomic insertions at the
319 head of the queue. */
321 static void wait_node_dequeue(struct wait_node **pp_head,
322 struct wait_node **pp_node,
323 struct wait_node *p_node)
325 /* If the node is being deleted from the head of the
326 list, it must be deleted using atomic compare-and-swap.
327 Otherwise it can be deleted in the straightforward way. */
329 if (pp_node == pp_head) {
330 /* We don't need a read barrier between these next two loads,
331 because it is assumed that the caller has already ensured
332 the stability of *p_node with respect to p_node. */
334 long oldvalue = (long) p_node;
335 long newvalue = (long) p_node->next;
337 if (__compare_and_swap((long *) pp_node, oldvalue, newvalue))
340 /* Oops! Compare and swap failed, which means the node is
341 no longer first. We delete it using the ordinary method. But we don't
342 know the identity of the node which now holds the pointer to the node
343 being deleted, so we must search from the beginning. */
345 for (pp_node = pp_head; p_node != *pp_node; ) {
346 pp_node = &(*pp_node)->next;
347 READ_MEMORY_BARRIER(); /* Stabilize *pp_node for next iteration. */
351 *pp_node = p_node->next;
357 void __pthread_alt_lock(struct _pthread_fastlock * lock,
360 #if defined HAS_COMPARE_AND_SWAP
361 long oldstatus, newstatus;
363 struct wait_node wait_node;
365 #if defined TEST_FOR_COMPARE_AND_SWAP
366 if (!__pthread_has_cas)
368 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
370 int suspend_needed = 0;
371 __pthread_acquire(&lock->__spinlock);
373 if (lock->__status == 0)
377 self = thread_self();
379 wait_node.abandoned = 0;
380 wait_node.next = (struct wait_node *) lock->__status;
381 wait_node.thr = self;
382 lock->__status = (long) &wait_node;
386 __pthread_release(&lock->__spinlock);
394 #if defined HAS_COMPARE_AND_SWAP
396 oldstatus = lock->__status;
397 if (oldstatus == 0) {
401 self = thread_self();
402 wait_node.thr = self;
403 newstatus = (long) &wait_node;
405 wait_node.abandoned = 0;
406 wait_node.next = (struct wait_node *) oldstatus;
407 /* Make sure the store in wait_node.next completes before performing
408 the compare-and-swap */
410 } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
412 /* Suspend. Note that unlike in __pthread_lock, we don't worry
413 here about spurious wakeup. That's because this lock is not
414 used in situations where that can happen; the restart can
415 only come from the previous lock owner. */
420 READ_MEMORY_BARRIER();
424 /* Timed-out lock operation; returns 0 to indicate timeout. */
426 int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
427 pthread_descr self, const struct timespec *abstime)
430 #if defined HAS_COMPARE_AND_SWAP
433 struct wait_node *p_wait_node = wait_node_alloc();
435 /* Out of memory, just give up and do ordinary lock. */
436 if (p_wait_node == 0) {
437 __pthread_alt_lock(lock, self);
441 #if defined TEST_FOR_COMPARE_AND_SWAP
442 if (!__pthread_has_cas)
444 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
446 __pthread_acquire(&lock->__spinlock);
448 if (lock->__status == 0)
452 self = thread_self();
454 p_wait_node->abandoned = 0;
455 p_wait_node->next = (struct wait_node *) lock->__status;
456 p_wait_node->thr = self;
457 lock->__status = (long) p_wait_node;
458 oldstatus = 1; /* force suspend */
461 __pthread_release(&lock->__spinlock);
466 #if defined HAS_COMPARE_AND_SWAP
468 oldstatus = lock->__status;
469 if (oldstatus == 0) {
473 self = thread_self();
474 p_wait_node->thr = self;
475 newstatus = (long) p_wait_node;
477 p_wait_node->abandoned = 0;
478 p_wait_node->next = (struct wait_node *) oldstatus;
479 /* Make sure the store in wait_node.next completes before performing
480 the compare-and-swap */
482 } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
485 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
489 /* If we did not get the lock, do a timed suspend. If we wake up due
490 to a timeout, then there is a race; the old lock owner may try
491 to remove us from the queue. This race is resolved by us and the owner
492 doing an atomic testandset() to change the state of the wait node from 0
493 to 1. If we succeed, then it's a timeout and we abandon the node in the
494 queue. If we fail, it means the owner gave us the lock. */
496 if (oldstatus != 0) {
497 if (timedsuspend(self, abstime) == 0) {
498 if (!testandset(&p_wait_node->abandoned))
499 return 0; /* Timeout! */
501 /* Eat oustanding resume from owner, otherwise wait_node_free() below
502 will race with owner's wait_node_dequeue(). */
507 wait_node_free(p_wait_node);
509 READ_MEMORY_BARRIER();
511 return 1; /* Got the lock! */
514 void __pthread_alt_unlock(struct _pthread_fastlock *lock)
516 struct wait_node *p_node, **pp_node, *p_max_prio, **pp_max_prio;
517 struct wait_node ** const pp_head = (struct wait_node **) &lock->__status;
520 WRITE_MEMORY_BARRIER();
522 #if defined TEST_FOR_COMPARE_AND_SWAP
523 if (!__pthread_has_cas)
525 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
527 __pthread_acquire(&lock->__spinlock);
533 /* If no threads are waiting for this lock, try to just
534 atomically release it. */
535 #if defined TEST_FOR_COMPARE_AND_SWAP
536 if (!__pthread_has_cas)
538 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
540 if (lock->__status == 0 || lock->__status == 1) {
547 #if defined TEST_FOR_COMPARE_AND_SWAP
551 #if defined HAS_COMPARE_AND_SWAP
553 long oldstatus = lock->__status;
554 if (oldstatus == 0 || oldstatus == 1) {
555 if (__compare_and_swap_with_release_semantics (&lock->__status, oldstatus, 0))
563 /* Process the entire queue of wait nodes. Remove all abandoned
564 wait nodes and put them into the global free queue, and
565 remember the one unabandoned node which refers to the thread
566 having the highest priority. */
568 pp_max_prio = pp_node = pp_head;
569 p_max_prio = p_node = *pp_head;
572 READ_MEMORY_BARRIER(); /* Prevent access to stale data through p_node */
574 while (p_node != (struct wait_node *) 1) {
577 if (p_node->abandoned) {
578 /* Remove abandoned node. */
579 #if defined TEST_FOR_COMPARE_AND_SWAP
580 if (!__pthread_has_cas)
582 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
583 *pp_node = p_node->next;
585 #if defined TEST_FOR_COMPARE_AND_SWAP
588 #if defined HAS_COMPARE_AND_SWAP
589 wait_node_dequeue(pp_head, pp_node, p_node);
591 wait_node_free(p_node);
592 /* Note that the next assignment may take us to the beginning
593 of the queue, to newly inserted nodes, if pp_node == pp_head.
594 In that case we need a memory barrier to stabilize the first of
597 if (pp_node == pp_head)
598 READ_MEMORY_BARRIER(); /* No stale reads through p_node */
600 } else if ((prio = p_node->thr->p_priority) >= maxprio) {
601 /* Otherwise remember it if its thread has a higher or equal priority
602 compared to that of any node seen thus far. */
604 pp_max_prio = pp_node;
608 /* This canno6 jump backward in the list, so no further read
609 barrier is needed. */
610 pp_node = &p_node->next;
614 /* If all threads abandoned, go back to top */
615 if (maxprio == INT_MIN)
618 ASSERT (p_max_prio != (struct wait_node *) 1);
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. */
627 if (!testandset(&p_max_prio->abandoned)) {
628 #if defined TEST_FOR_COMPARE_AND_SWAP
629 if (!__pthread_has_cas)
631 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
632 *pp_max_prio = p_max_prio->next;
634 #if defined TEST_FOR_COMPARE_AND_SWAP
637 #if defined HAS_COMPARE_AND_SWAP
638 wait_node_dequeue(pp_head, pp_max_prio, p_max_prio);
640 restart(p_max_prio->thr);
645 #if defined TEST_FOR_COMPARE_AND_SWAP
646 if (!__pthread_has_cas)
648 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
650 __pthread_release(&lock->__spinlock);
656 /* Compare-and-swap emulation with a spinlock */
658 #ifdef TEST_FOR_COMPARE_AND_SWAP
659 int __pthread_has_cas = 0;
662 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
664 int __pthread_compare_and_swap(long * ptr, long oldval, long newval,
669 __pthread_acquire(spinlock);
671 if (*ptr == oldval) {
672 *ptr = newval; res = 1;
677 __pthread_release(spinlock);
684 /* The retry strategy is as follows:
685 - We test and set the spinlock MAX_SPIN_COUNT times, calling
686 sched_yield() each time. This gives ample opportunity for other
687 threads with priority >= our priority to make progress and
688 release the spinlock.
689 - If a thread with priority < our priority owns the spinlock,
690 calling sched_yield() repeatedly is useless, since we're preventing
691 the owning thread from making progress and releasing the spinlock.
692 So, after MAX_SPIN_LOCK attemps, we suspend the calling thread
693 using nanosleep(). This again should give time to the owning thread
694 for releasing the spinlock.
695 Notice that the nanosleep() interval must not be too small,
696 since the kernel does busy-waiting for short intervals in a realtime
697 process (!). The smallest duration that guarantees thread
698 suspension is currently 2ms.
699 - When nanosleep() returns, we try again, doing MAX_SPIN_COUNT
700 sched_yield(), then sleeping again if needed. */
702 static void __pthread_acquire(int * spinlock)
707 READ_MEMORY_BARRIER();
709 while (testandset(spinlock)) {
710 if (cnt < MAX_SPIN_COUNT) {
715 tm.tv_nsec = SPIN_SLEEP_DURATION;
716 nanosleep(&tm, NULL);