2002-08-02 Roland McGrath <roland@redhat.com>
[kopensolaris-gnu/glibc.git] / linuxthreads / spinlock.c
index 38d6b8e..582a95c 100644 (file)
 #include "spinlock.h"
 #include "restart.h"
 
-#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 static void __pthread_acquire(int * spinlock);
-#endif
+
+static inline void __pthread_release(int * spinlock)
+{
+  WRITE_MEMORY_BARRIER();
+  *spinlock = __LT_SPINLOCK_INIT;
+  __asm __volatile ("" : "=m" (*spinlock) : "0" (*spinlock));
+}
 
 
 /* The status field of a spinlock is a pointer whose least significant
@@ -57,8 +62,8 @@ void internal_function __pthread_lock(struct _pthread_fastlock * lock,
 {
 #if defined HAS_COMPARE_AND_SWAP
   long oldstatus, newstatus;
-  int successful_seizure, spurious_wakeup_count = 0;
-  int spin_count = 0;
+  int successful_seizure, spurious_wakeup_count;
+  int spin_count;
 #endif
 
 #if defined TEST_FOR_COMPARE_AND_SWAP
@@ -72,6 +77,14 @@ void internal_function __pthread_lock(struct _pthread_fastlock * lock,
 #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;
+
 again:
 
   /* On SMP, try spinning to get the lock. */
@@ -79,15 +92,23 @@ again:
   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) : "0" (lock->__status));
     }
 
     lock->__spinlock += (spin_count - lock->__spinlock) / 8;
@@ -138,6 +159,8 @@ again:
   /* Put back any resumes we caught that don't belong to us. */
   while (spurious_wakeup_count--)
     restart(self);
+
+  READ_MEMORY_BARRIER();
 #endif
 }
 
@@ -154,16 +177,15 @@ int __pthread_unlock(struct _pthread_fastlock * lock)
 #endif
 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
   {
-    WRITE_MEMORY_BARRIER();
-    lock->__spinlock = 0;
+    __pthread_release(&lock->__spinlock);
     return 0;
   }
 #endif
 
 #if defined HAS_COMPARE_AND_SWAP
-again:
-  oldstatus = lock->__status;
+  WRITE_MEMORY_BARRIER();
 
+again:
   while ((oldstatus = lock->__status) == 1) {
     if (__compare_and_swap_with_release_semantics(&lock->__status,
        oldstatus, 0))
@@ -175,23 +197,26 @@ again:
   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);
-    /* Prevent reordering of the load of lock->__status above and the
-       load of *ptr below, as well as reordering of *ptr between
-       several iterations of the while loop.  Some processors (e.g.
-       multiprocessor Alphas) could perform such reordering even though
-       the loads are dependent. */
-    READ_MEMORY_BARRIER();
     thr = *ptr;
   }
-  /* Prevent reordering of the load of lock->__status above and
-     thr->p_nextlock below */
-  READ_MEMORY_BARRIER();
+
   /* 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
@@ -210,15 +235,21 @@ again:
     thr = *maxptr;
     *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));
   }
-  /* Prevent reordering of store to *maxptr above and store to thr->p_nextlock
-     below */
-  WRITE_MEMORY_BARRIER();
-  /* Wake up the selected waiting thread */
+
+  /* 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);
 
@@ -242,9 +273,7 @@ struct wait_node {
 };
 
 static long wait_node_free_list;
-#if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
 static int wait_node_free_list_spinlock;
-#endif
 
 /* 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
@@ -254,15 +283,6 @@ static int wait_node_free_list_spinlock;
 
 static struct wait_node *wait_node_alloc(void)
 {
-#if defined HAS_COMPARE_AND_SWAP
-  long oldvalue, newvalue;
-#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
-  {
     struct wait_node *new_node = 0;
 
     __pthread_acquire(&wait_node_free_list_spinlock);
@@ -271,28 +291,12 @@ static struct wait_node *wait_node_alloc(void)
       wait_node_free_list = (long) new_node->next;
     }
     WRITE_MEMORY_BARRIER();
-    wait_node_free_list_spinlock = 0;
+    __pthread_release(&wait_node_free_list_spinlock);
 
     if (new_node == 0)
       return malloc(sizeof *wait_node_alloc());
 
     return new_node;
-  }
-#endif
-
-#if defined HAS_COMPARE_AND_SWAP
-  do {
-    oldvalue = wait_node_free_list;
-
-    if (oldvalue == 0)
-      return malloc(sizeof *wait_node_alloc());
-
-    newvalue = (long) ((struct wait_node *) oldvalue)->next;
-    WRITE_MEMORY_BARRIER();
-  } while (! __compare_and_swap(&wait_node_free_list, oldvalue, newvalue));
-
-  return (struct wait_node *) oldvalue;
-#endif
 }
 
 /* Return a node to the head of the free list using an atomic
@@ -300,32 +304,12 @@ static struct wait_node *wait_node_alloc(void)
 
 static void wait_node_free(struct wait_node *wn)
 {
-#if defined HAS_COMPARE_AND_SWAP
-  long oldvalue, newvalue;
-#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(&wait_node_free_list_spinlock);
     wn->next = (struct wait_node *) wait_node_free_list;
     wait_node_free_list = (long) wn;
     WRITE_MEMORY_BARRIER();
-    wait_node_free_list_spinlock = 0;
+    __pthread_release(&wait_node_free_list_spinlock);
     return;
-  }
-#endif
-
-#if defined HAS_COMPARE_AND_SWAP
-  do {
-    oldvalue = wait_node_free_list;
-    wn->next = (struct wait_node *) oldvalue;
-    newvalue = (long) wn;
-    WRITE_MEMORY_BARRIER();
-  } while (! __compare_and_swap(&wait_node_free_list, oldvalue, newvalue));
-#endif
 }
 
 #if defined HAS_COMPARE_AND_SWAP
@@ -343,9 +327,13 @@ static void wait_node_dequeue(struct wait_node **pp_head,
      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;
 
@@ -354,8 +342,10 @@ static void wait_node_dequeue(struct wait_node **pp_head,
        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; *pp_node != p_node; pp_node = &(*pp_node)->next)
-      ; /* null body */
+    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;
@@ -388,12 +378,12 @@ void __pthread_alt_lock(struct _pthread_fastlock * lock,
 
       wait_node.abandoned = 0;
       wait_node.next = (struct wait_node *) lock->__status;
-      wait_node.thr = self = thread_self();
+      wait_node.thr = self;
+      lock->__status = (long) &wait_node;
       suspend_needed = 1;
     }
 
-    WRITE_MEMORY_BARRIER();
-    lock->__spinlock = 0;
+    __pthread_release(&lock->__spinlock);
 
     if (suspend_needed)
       suspend (self);
@@ -408,7 +398,8 @@ void __pthread_alt_lock(struct _pthread_fastlock * lock,
       newstatus = 1;
     } else {
       if (self == NULL)
-       wait_node.thr = self = thread_self();
+       self = thread_self();
+      wait_node.thr = self;
       newstatus = (long) &wait_node;
     }
     wait_node.abandoned = 0;
@@ -416,8 +407,7 @@ void __pthread_alt_lock(struct _pthread_fastlock * lock,
     /* 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,
-                             &lock->__spinlock));
+  } 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
@@ -426,6 +416,8 @@ void __pthread_alt_lock(struct _pthread_fastlock * lock,
 
   if (oldstatus != 0)
     suspend(self);
+
+  READ_MEMORY_BARRIER();
 #endif
 }
 
@@ -434,7 +426,7 @@ void __pthread_alt_lock(struct _pthread_fastlock * lock,
 int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
                            pthread_descr self, const struct timespec *abstime)
 {
-  long oldstatus;
+  long oldstatus = 0;
 #if defined HAS_COMPARE_AND_SWAP
   long newstatus;
 #endif
@@ -461,12 +453,12 @@ int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
 
       p_wait_node->abandoned = 0;
       p_wait_node->next = (struct wait_node *) lock->__status;
-      p_wait_node->thr = self = thread_self();
+      p_wait_node->thr = self;
+      lock->__status = (long) p_wait_node;
+      oldstatus = 1; /* force suspend */
     }
 
-    WRITE_MEMORY_BARRIER();
-    lock->__spinlock = 0;
-    oldstatus = 1; /* force suspend */
+    __pthread_release(&lock->__spinlock);
     goto suspend;
   }
 #endif
@@ -478,7 +470,8 @@ int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
       newstatus = 1;
     } else {
       if (self == NULL)
-       p_wait_node->thr = self = thread_self();
+       self = thread_self();
+      p_wait_node->thr = self;
       newstatus = (long) p_wait_node;
     }
     p_wait_node->abandoned = 0;
@@ -486,8 +479,7 @@ int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
     /* 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,
-                             &lock->__spinlock));
+  } while(! __compare_and_swap(&lock->__status, oldstatus, newstatus));
 #endif
 
 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
@@ -514,6 +506,8 @@ int __pthread_alt_timedlock(struct _pthread_fastlock * lock,
 
   wait_node_free(p_wait_node);
 
+  READ_MEMORY_BARRIER();
+
   return 1; /* Got the lock! */
 }
 
@@ -523,6 +517,8 @@ void __pthread_alt_unlock(struct _pthread_fastlock *lock)
   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
@@ -573,6 +569,8 @@ void __pthread_alt_unlock(struct _pthread_fastlock *lock)
     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;
 
@@ -591,8 +589,13 @@ void __pthread_alt_unlock(struct _pthread_fastlock *lock)
          wait_node_dequeue(pp_head, pp_node, p_node);
 #endif
        wait_node_free(p_node);
-       READ_MEMORY_BARRIER();
+       /* 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
@@ -602,13 +605,12 @@ void __pthread_alt_unlock(struct _pthread_fastlock *lock)
        p_max_prio = p_node;
       }
 
+      /* This canno6 jump backward in the list, so no further read
+         barrier is needed. */
       pp_node = &p_node->next;
-      READ_MEMORY_BARRIER();
       p_node = *pp_node;
     }
 
-    READ_MEMORY_BARRIER();
-
     /* If all threads abandoned, go back to top */
     if (maxprio == INT_MIN)
       continue;
@@ -635,7 +637,6 @@ void __pthread_alt_unlock(struct _pthread_fastlock *lock)
 #if defined HAS_COMPARE_AND_SWAP
        wait_node_dequeue(pp_head, pp_max_prio, p_max_prio);
 #endif
-      WRITE_MEMORY_BARRIER();
       restart(p_max_prio->thr);
       break;
     }
@@ -646,8 +647,7 @@ void __pthread_alt_unlock(struct _pthread_fastlock *lock)
 #endif
 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
   {
-    WRITE_MEMORY_BARRIER();
-    lock->__spinlock = 0;
+    __pthread_release(&lock->__spinlock);
   }
 #endif
 }
@@ -665,20 +665,21 @@ int __pthread_compare_and_swap(long * ptr, long oldval, long newval,
                                int * spinlock)
 {
   int res;
-  if (testandset(spinlock)) __pthread_acquire(spinlock);
+
+  __pthread_acquire(spinlock);
+
   if (*ptr == oldval) {
     *ptr = newval; res = 1;
   } else {
     res = 0;
   }
-  /* Prevent reordering of store to *ptr above and store to *spinlock below */
-  WRITE_MEMORY_BARRIER();
-  *spinlock = 0;
+
+  __pthread_release(spinlock);
+
   return res;
 }
 
-/* This function is called if the inlined test-and-set
-   in __pthread_compare_and_swap() failed */
+#endif
 
 /* The retry strategy is as follows:
    - We test and set the spinlock MAX_SPIN_COUNT times, calling
@@ -703,6 +704,8 @@ 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();
@@ -715,5 +718,3 @@ static void __pthread_acquire(int * spinlock)
     }
   }
 }
-
-#endif