diff options
Diffstat (limited to 'libpthread/linuxthreads.old/spinlock.c')
| -rw-r--r-- | libpthread/linuxthreads.old/spinlock.c | 723 |
1 files changed, 723 insertions, 0 deletions
diff --git a/libpthread/linuxthreads.old/spinlock.c b/libpthread/linuxthreads.old/spinlock.c new file mode 100644 index 000000000..cdf45f195 --- /dev/null +++ b/libpthread/linuxthreads.old/spinlock.c @@ -0,0 +1,723 @@ +/* Linuxthreads - a simple clone()-based implementation of Posix */ +/* threads for Linux. */ +/* Copyright (C) 1998 Xavier Leroy (Xavier.Leroy@inria.fr) */ +/* */ +/* This program is free software; you can redistribute it and/or */ +/* modify it under the terms of the GNU Library General Public License */ +/* as published by the Free Software Foundation; either version 2 */ +/* of the License, or (at your option) any later version. */ +/* */ +/* This program is distributed in the hope that it will be useful, */ +/* but WITHOUT ANY WARRANTY; without even the implied warranty of */ +/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */ +/* GNU Library General Public License for more details. */ + +/* Internal locks */ + +#define __FORCE_GLIBC +#include <features.h> +#include <errno.h> +#include <sched.h> +#include <time.h> +#include <stdlib.h> +#include <limits.h> +#include "pthread.h" +#include "internals.h" +#include "spinlock.h" +#include "restart.h" + +static void __pthread_acquire(int * spinlock); + +static inline void __pthread_release(int * spinlock) +{ + WRITE_MEMORY_BARRIER(); + *spinlock = __LT_SPINLOCK_INIT; + __asm __volatile ("" : "=m" (*spinlock) : "m" (*spinlock)); +} + + +/* The status field of a spinlock is a pointer whose least significant + bit is a locked flag. + + Thus the field values have the following meanings: + + status == 0: spinlock is free + status == 1: spinlock is taken; no thread is waiting on it + + (status & 1) == 1: spinlock is taken and (status & ~1L) is a + pointer to the first waiting thread; other + waiting threads are linked via the p_nextlock + field. + (status & 1) == 0: same as above, but spinlock is not taken. + + The waiting list is not sorted by priority order. + Actually, we always insert at top of list (sole insertion mode + that can be performed without locking). + For __pthread_unlock, we perform a linear search in the list + to find the highest-priority, oldest waiting thread. + This is safe because there are no concurrent __pthread_unlock + operations -- only the thread that locked the mutex can unlock it. */ + + +void internal_function __pthread_lock(struct _pthread_fastlock * lock, + pthread_descr self) +{ +#if defined HAS_COMPARE_AND_SWAP + long oldstatus, newstatus; + int successful_seizure, spurious_wakeup_count; + int spin_count; +#endif + +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + __pthread_acquire(&lock->__spinlock); + return; + } +#endif + +#if defined HAS_COMPARE_AND_SWAP + /* First try it without preparation. Maybe it's a completely + uncontested lock. */ + if (lock->__status == 0 && __compare_and_swap (&lock->__status, 0, 1)) + return; + + spurious_wakeup_count = 0; + spin_count = 0; + + /* On SMP, try spinning to get the lock. */ +#if 0 + if (__pthread_smp_kernel) { + int max_count = lock->__spinlock * 2 + 10; + + if (max_count > MAX_ADAPTIVE_SPIN_COUNT) + max_count = MAX_ADAPTIVE_SPIN_COUNT; + + for (spin_count = 0; spin_count < max_count; spin_count++) { + if (((oldstatus = lock->__status) & 1) == 0) { + if(__compare_and_swap(&lock->__status, oldstatus, oldstatus | 1)) + { + if (spin_count) + lock->__spinlock += (spin_count - lock->__spinlock) / 8; + READ_MEMORY_BARRIER(); + return; + } + } +#ifdef BUSY_WAIT_NOP + BUSY_WAIT_NOP; +#endif + __asm __volatile ("" : "=m" (lock->__status) : "m" (lock->__status)); + } + + lock->__spinlock += (spin_count - lock->__spinlock) / 8; + } +#endif + +again: + + /* No luck, try once more or suspend. */ + + do { + oldstatus = lock->__status; + successful_seizure = 0; + + if ((oldstatus & 1) == 0) { + newstatus = oldstatus | 1; + successful_seizure = 1; + } else { + if (self == NULL) + self = thread_self(); + newstatus = (long) self | 1; + } + + if (self != NULL) { + THREAD_SETMEM(self, p_nextlock, (pthread_descr) (oldstatus)); + /* Make sure the store in p_nextlock completes before performing + the compare-and-swap */ + MEMORY_BARRIER(); + } + } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus)); + + /* Suspend with guard against spurious wakeup. + This can happen in pthread_cond_timedwait_relative, when the thread + wakes up due to timeout and is still on the condvar queue, and then + locks the queue to remove itself. At that point it may still be on the + queue, and may be resumed by a condition signal. */ + + if (!successful_seizure) { + for (;;) { + suspend(self); + if (self->p_nextlock != NULL) { + /* Count resumes that don't belong to us. */ + spurious_wakeup_count++; + continue; + } + break; + } + goto again; + } + + /* Put back any resumes we caught that don't belong to us. */ + while (spurious_wakeup_count--) + restart(self); + + READ_MEMORY_BARRIER(); +#endif +} + +int __pthread_unlock(struct _pthread_fastlock * lock) +{ +#if defined HAS_COMPARE_AND_SWAP + long oldstatus; + pthread_descr thr, * ptr, * maxptr; + int maxprio; +#endif + +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + __pthread_release(&lock->__spinlock); + return 0; + } +#endif + +#if defined HAS_COMPARE_AND_SWAP + WRITE_MEMORY_BARRIER(); + +again: + while ((oldstatus = lock->__status) == 1) { + if (__compare_and_swap_with_release_semantics(&lock->__status, + oldstatus, 0)) + return 0; + } + + /* Find thread in waiting queue with maximal priority */ + ptr = (pthread_descr *) &lock->__status; + thr = (pthread_descr) (oldstatus & ~1L); + maxprio = 0; + maxptr = ptr; + + /* Before we iterate over the wait queue, we need to execute + a read barrier, otherwise we may read stale contents of nodes that may + just have been inserted by other processors. One read barrier is enough to + ensure we have a stable list; we don't need one for each pointer chase + through the list, because we are the owner of the lock; other threads + can only add nodes at the front; if a front node is consistent, + the ones behind it must also be. */ + + READ_MEMORY_BARRIER(); + + while (thr != 0) { + if (thr->p_priority >= maxprio) { + maxptr = ptr; + maxprio = thr->p_priority; + } + ptr = &(thr->p_nextlock); + thr = (pthread_descr)((long)(thr->p_nextlock) & ~1L); + } + + /* Remove max prio thread from waiting list. */ + if (maxptr == (pthread_descr *) &lock->__status) { + /* If max prio thread is at head, remove it with compare-and-swap + to guard against concurrent lock operation. This removal + also has the side effect of marking the lock as released + because the new status comes from thr->p_nextlock whose + least significant bit is clear. */ + thr = (pthread_descr) (oldstatus & ~1L); + if (! __compare_and_swap_with_release_semantics + (&lock->__status, oldstatus, (long)(thr->p_nextlock) & ~1L)) + goto again; + } else { + /* No risk of concurrent access, remove max prio thread normally. + But in this case we must also flip the least significant bit + of the status to mark the lock as released. */ + thr = (pthread_descr)((long)*maxptr & ~1L); + *maxptr = thr->p_nextlock; + + /* Ensure deletion from linked list completes before we + release the lock. */ + WRITE_MEMORY_BARRIER(); + + do { + oldstatus = lock->__status; + } while (!__compare_and_swap_with_release_semantics(&lock->__status, + oldstatus, oldstatus & ~1L)); + } + + /* Wake up the selected waiting thread. Woken thread can check + its own p_nextlock field for NULL to detect that it has been removed. No + barrier is needed here, since restart() and suspend() take + care of memory synchronization. */ + + thr->p_nextlock = NULL; + restart(thr); + + return 0; +#endif +} + +/* + * Alternate fastlocks do not queue threads directly. Instead, they queue + * these wait queue node structures. When a timed wait wakes up due to + * a timeout, it can leave its wait node in the queue (because there + * is no safe way to remove from the quue). Some other thread will + * deallocate the abandoned node. + */ + + +struct wait_node { + struct wait_node *next; /* Next node in null terminated linked list */ + pthread_descr thr; /* The thread waiting with this node */ + int abandoned; /* Atomic flag */ +}; + +static long wait_node_free_list; +static int wait_node_free_list_spinlock; + +/* Allocate a new node from the head of the free list using an atomic + operation, or else using malloc if that list is empty. A fundamental + assumption here is that we can safely access wait_node_free_list->next. + That's because we never free nodes once we allocate them, so a pointer to a + node remains valid indefinitely. */ + +static struct wait_node *wait_node_alloc(void) +{ + struct wait_node *new_node = 0; + + __pthread_acquire(&wait_node_free_list_spinlock); + if (wait_node_free_list != 0) { + new_node = (struct wait_node *) wait_node_free_list; + wait_node_free_list = (long) new_node->next; + } + WRITE_MEMORY_BARRIER(); + __pthread_release(&wait_node_free_list_spinlock); + + if (new_node == 0) + return malloc(sizeof *wait_node_alloc()); + + return new_node; +} + +/* Return a node to the head of the free list using an atomic + operation. */ + +static void wait_node_free(struct wait_node *wn) +{ + __pthread_acquire(&wait_node_free_list_spinlock); + wn->next = (struct wait_node *) wait_node_free_list; + wait_node_free_list = (long) wn; + WRITE_MEMORY_BARRIER(); + __pthread_release(&wait_node_free_list_spinlock); + return; +} + +#if defined HAS_COMPARE_AND_SWAP + +/* Remove a wait node from the specified queue. It is assumed + that the removal takes place concurrently with only atomic insertions at the + head of the queue. */ + +static void wait_node_dequeue(struct wait_node **pp_head, + struct wait_node **pp_node, + struct wait_node *p_node) +{ + /* If the node is being deleted from the head of the + list, it must be deleted using atomic compare-and-swap. + Otherwise it can be deleted in the straightforward way. */ + + if (pp_node == pp_head) { + /* We don't need a read barrier between these next two loads, + because it is assumed that the caller has already ensured + the stability of *p_node with respect to p_node. */ + + long oldvalue = (long) p_node; + long newvalue = (long) p_node->next; + + if (__compare_and_swap((long *) pp_node, oldvalue, newvalue)) + return; + + /* Oops! Compare and swap failed, which means the node is + no longer first. We delete it using the ordinary method. But we don't + know the identity of the node which now holds the pointer to the node + being deleted, so we must search from the beginning. */ + + for (pp_node = pp_head; p_node != *pp_node; ) { + pp_node = &(*pp_node)->next; + READ_MEMORY_BARRIER(); /* Stabilize *pp_node for next iteration. */ + } + } + + *pp_node = p_node->next; + return; +} + +#endif + +void __pthread_alt_lock(struct _pthread_fastlock * lock, + pthread_descr self) +{ +#if defined HAS_COMPARE_AND_SWAP + long oldstatus, newstatus; +#endif + struct wait_node wait_node; + +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + int suspend_needed = 0; + __pthread_acquire(&lock->__spinlock); + + if (lock->__status == 0) + lock->__status = 1; + else { + if (self == NULL) + self = thread_self(); + + wait_node.abandoned = 0; + wait_node.next = (struct wait_node *) lock->__status; + wait_node.thr = self; + lock->__status = (long) &wait_node; + suspend_needed = 1; + } + + __pthread_release(&lock->__spinlock); + + if (suspend_needed) + suspend (self); + return; + } +#endif + +#if defined HAS_COMPARE_AND_SWAP + do { + oldstatus = lock->__status; + if (oldstatus == 0) { + newstatus = 1; + } else { + if (self == NULL) + self = thread_self(); + wait_node.thr = self; + newstatus = (long) &wait_node; + } + wait_node.abandoned = 0; + wait_node.next = (struct wait_node *) oldstatus; + /* Make sure the store in wait_node.next completes before performing + the compare-and-swap */ + MEMORY_BARRIER(); + } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus)); + + /* Suspend. Note that unlike in __pthread_lock, we don't worry + here about spurious wakeup. That's because this lock is not + used in situations where that can happen; the restart can + only come from the previous lock owner. */ + + if (oldstatus != 0) + suspend(self); + + READ_MEMORY_BARRIER(); +#endif +} + +/* Timed-out lock operation; returns 0 to indicate timeout. */ + +int __pthread_alt_timedlock(struct _pthread_fastlock * lock, + pthread_descr self, const struct timespec *abstime) +{ + long oldstatus = 0; +#if defined HAS_COMPARE_AND_SWAP + long newstatus; +#endif + struct wait_node *p_wait_node = wait_node_alloc(); + + /* Out of memory, just give up and do ordinary lock. */ + if (p_wait_node == 0) { + __pthread_alt_lock(lock, self); + return 1; + } + +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + __pthread_acquire(&lock->__spinlock); + + if (lock->__status == 0) + lock->__status = 1; + else { + if (self == NULL) + self = thread_self(); + + p_wait_node->abandoned = 0; + p_wait_node->next = (struct wait_node *) lock->__status; + p_wait_node->thr = self; + lock->__status = (long) p_wait_node; + oldstatus = 1; /* force suspend */ + } + + __pthread_release(&lock->__spinlock); + goto suspend; + } +#endif + +#if defined HAS_COMPARE_AND_SWAP + do { + oldstatus = lock->__status; + if (oldstatus == 0) { + newstatus = 1; + } else { + if (self == NULL) + self = thread_self(); + p_wait_node->thr = self; + newstatus = (long) p_wait_node; + } + p_wait_node->abandoned = 0; + p_wait_node->next = (struct wait_node *) oldstatus; + /* Make sure the store in wait_node.next completes before performing + the compare-and-swap */ + MEMORY_BARRIER(); + } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus)); +#endif + +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + suspend: +#endif + + /* If we did not get the lock, do a timed suspend. If we wake up due + to a timeout, then there is a race; the old lock owner may try + to remove us from the queue. This race is resolved by us and the owner + doing an atomic testandset() to change the state of the wait node from 0 + to 1. If we succeed, then it's a timeout and we abandon the node in the + queue. If we fail, it means the owner gave us the lock. */ + + if (oldstatus != 0) { + if (timedsuspend(self, abstime) == 0) { + if (!testandset(&p_wait_node->abandoned)) + return 0; /* Timeout! */ + + /* Eat oustanding resume from owner, otherwise wait_node_free() below + will race with owner's wait_node_dequeue(). */ + suspend(self); + } + } + + wait_node_free(p_wait_node); + + READ_MEMORY_BARRIER(); + + return 1; /* Got the lock! */ +} + +void __pthread_alt_unlock(struct _pthread_fastlock *lock) +{ + struct wait_node *p_node, **pp_node, *p_max_prio, **pp_max_prio; + struct wait_node ** const pp_head = (struct wait_node **) &lock->__status; + int maxprio; + + WRITE_MEMORY_BARRIER(); + +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + __pthread_acquire(&lock->__spinlock); + } +#endif + + while (1) { + + /* If no threads are waiting for this lock, try to just + atomically release it. */ +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + if (lock->__status == 0 || lock->__status == 1) { + lock->__status = 0; + break; + } + } +#endif + +#if defined TEST_FOR_COMPARE_AND_SWAP + else +#endif + +#if defined HAS_COMPARE_AND_SWAP + { + long oldstatus = lock->__status; + if (oldstatus == 0 || oldstatus == 1) { + if (__compare_and_swap_with_release_semantics (&lock->__status, oldstatus, 0)) + break; + else + continue; + } + } +#endif + + /* Process the entire queue of wait nodes. Remove all abandoned + wait nodes and put them into the global free queue, and + remember the one unabandoned node which refers to the thread + having the highest priority. */ + + pp_max_prio = pp_node = pp_head; + p_max_prio = p_node = *pp_head; + maxprio = INT_MIN; + + READ_MEMORY_BARRIER(); /* Prevent access to stale data through p_node */ + + while (p_node != (struct wait_node *) 1) { + int prio; + + if (p_node->abandoned) { + /* Remove abandoned node. */ +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + *pp_node = p_node->next; +#endif +#if defined TEST_FOR_COMPARE_AND_SWAP + else +#endif +#if defined HAS_COMPARE_AND_SWAP + wait_node_dequeue(pp_head, pp_node, p_node); +#endif + wait_node_free(p_node); + /* Note that the next assignment may take us to the beginning + of the queue, to newly inserted nodes, if pp_node == pp_head. + In that case we need a memory barrier to stabilize the first of + these new nodes. */ + p_node = *pp_node; + if (pp_node == pp_head) + READ_MEMORY_BARRIER(); /* No stale reads through p_node */ + continue; + } else if ((prio = p_node->thr->p_priority) >= maxprio) { + /* Otherwise remember it if its thread has a higher or equal priority + compared to that of any node seen thus far. */ + maxprio = prio; + pp_max_prio = pp_node; + p_max_prio = p_node; + } + + /* This canno6 jump backward in the list, so no further read + barrier is needed. */ + pp_node = &p_node->next; + p_node = *pp_node; + } + + /* If all threads abandoned, go back to top */ + if (maxprio == INT_MIN) + continue; + + ASSERT (p_max_prio != (struct wait_node *) 1); + + /* Now we want to to remove the max priority thread's wait node from + the list. Before we can do this, we must atomically try to change the + node's abandon state from zero to nonzero. If we succeed, that means we + have the node that we will wake up. If we failed, then it means the + thread timed out and abandoned the node in which case we repeat the + whole unlock operation. */ + + if (!testandset(&p_max_prio->abandoned)) { +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + *pp_max_prio = p_max_prio->next; +#endif +#if defined TEST_FOR_COMPARE_AND_SWAP + else +#endif +#if defined HAS_COMPARE_AND_SWAP + wait_node_dequeue(pp_head, pp_max_prio, p_max_prio); +#endif + restart(p_max_prio->thr); + break; + } + } + +#if defined TEST_FOR_COMPARE_AND_SWAP + if (!__pthread_has_cas) +#endif +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + { + __pthread_release(&lock->__spinlock); + } +#endif +} + + +/* Compare-and-swap emulation with a spinlock */ + +#ifdef TEST_FOR_COMPARE_AND_SWAP +int __pthread_has_cas = 0; +#endif + +#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP + +int __pthread_compare_and_swap(long * ptr, long oldval, long newval, + int * spinlock) +{ + int res; + + __pthread_acquire(spinlock); + + if (*ptr == oldval) { + *ptr = newval; res = 1; + } else { + res = 0; + } + + __pthread_release(spinlock); + + return res; +} + +#endif + +/* The retry strategy is as follows: + - We test and set the spinlock MAX_SPIN_COUNT times, calling + sched_yield() each time. This gives ample opportunity for other + threads with priority >= our priority to make progress and + release the spinlock. + - If a thread with priority < our priority owns the spinlock, + calling sched_yield() repeatedly is useless, since we're preventing + the owning thread from making progress and releasing the spinlock. + So, after MAX_SPIN_LOCK attemps, we suspend the calling thread + using nanosleep(). This again should give time to the owning thread + for releasing the spinlock. + Notice that the nanosleep() interval must not be too small, + since the kernel does busy-waiting for short intervals in a realtime + process (!). The smallest duration that guarantees thread + suspension is currently 2ms. + - When nanosleep() returns, we try again, doing MAX_SPIN_COUNT + sched_yield(), then sleeping again if needed. */ + +static void __pthread_acquire(int * spinlock) +{ + int cnt = 0; + struct timespec tm; + + READ_MEMORY_BARRIER(); + + while (testandset(spinlock)) { + if (cnt < MAX_SPIN_COUNT) { + sched_yield(); + cnt++; + } else { + tm.tv_sec = 0; + tm.tv_nsec = SPIN_SLEEP_DURATION; + nanosleep(&tm, NULL); + cnt = 0; + } + } +} |