2.5-18.1

1 files changed, 0 insertions, 720 deletions

diff --git a/linuxthreads/spinlock.c b/linuxthreads/spinlock.c
deleted file mode 100644
index 08fff082ef..0000000000
--- a/linuxthreads/spinlock.c
+++ /dev/null
@@ -1,720 +0,0 @@
-/* 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 */
-
-#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 (__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;
-  }
-
-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;
-    }
-  }
-}