linuxthreads/semaphore.c

   1 /* Linuxthreads - a simple clone()-based implementation of Posix        */
   2 /* threads for Linux.                                                   */
   3 /* Copyright (C) 1996 Xavier Leroy (Xavier.Leroy@inria.fr)              */
   4 /*                                                                      */
   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.               */
   9 /*                                                                      */
  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.                 */
  14
  15 /* Semaphores a la POSIX 1003.1b */
  16
  17 #include "pthread.h"
  18 #include "semaphore.h"
  19 #include "internals.h"
  20 #include "restart.h"
  21
  22
  23 #if !defined HAS_COMPARE_AND_SWAP && !defined TEST_FOR_COMPARE_AND_SWAP
  24 /* If we have no atomic compare and swap, fake it using an extra spinlock.  */
  25
  26 #include "spinlock.h"
  27 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
  28 {
  29   int ret;
  30   acquire(&sem->sem_spinlock);
  31   ret = (sem->sem_status == oldval);
  32   if (ret) sem->sem_status = newval;
  33   release(&sem->sem_spinlock);
  34   return ret;
  35 }
  36
  37 #elif defined TEST_FOR_COMPARE_AND_SWAP
  38
  39 #include "spinlock.h"
  40 static int has_compare_and_swap = -1; /* to be determined at run-time */
  41
  42 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
  43 {
  44   int ret;
  45
  46   if (has_compare_and_swap == 1)
  47     return __compare_and_swap(&sem->sem_status, oldval, newval);
  48
  49   acquire(&sem->sem_spinlock);
  50   ret = (sem->sem_status == oldval);
  51   if (ret) sem->sem_status = newval;
  52   release(&sem->sem_spinlock);
  53   return ret;
  54 }
  55
  56 #else
  57 /* But if we do have an atomic compare and swap, use it!  */
  58
  59 static inline int sem_compare_and_swap(sem_t *sem, long oldval, long newval)
  60 {
  61   return __compare_and_swap(&sem->sem_status, oldval, newval);
  62 }
  63
  64 #endif
  65
  66
  67 /* The state of a semaphore is represented by a long int encoding
  68    either the semaphore count if >= 0 and no thread is waiting on it,
  69    or the head of the list of threads waiting for the semaphore.
  70    To distinguish the two cases, we encode the semaphore count N
  71    as 2N+1, so that it has the lowest bit set.
  72
  73    A sequence of sem_wait operations on a semaphore initialized to N
  74    result in the following successive states:
  75      2N+1, 2N-1, ..., 3, 1, &first_waiting_thread, &second_waiting_thread, ...
  76 */
  77
  78 static void sem_restart_list(pthread_descr waiting);
  79
  80 int sem_init(sem_t *sem, int pshared, unsigned int value)
  81 {
  82   if ((long)value > SEM_VALUE_MAX) {
  83     errno = EINVAL;
  84     return -1;
  85   }
  86   if (pshared) {
  87     errno = ENOSYS;
  88     return -1;
  89   }
  90 #ifdef TEST_FOR_COMPARE_AND_SWAP
  91   if (has_compare_and_swap == -1) {
  92     has_compare_and_swap = compare_and_swap_is_available();
  93   }
  94 #endif
  95 #if !defined HAS_COMPARE_AND_SWAP || defined TEST_FOR_COMPARE_AND_SWAP
  96   sem->sem_spinlock = 0;
  97 #endif
  98   sem->sem_status = ((long)value << 1) + 1;
  99   return 0;
 100 }
 101
 102 int sem_wait(sem_t * sem)
 103 {
 104   long oldstatus, newstatus;
 105   volatile pthread_descr self = thread_self();
 106   pthread_descr * th;
 107
 108   while (1) {
 109     do {
 110       oldstatus = sem->sem_status;
 111       if ((oldstatus & 1) && (oldstatus != 1))
 112         newstatus = oldstatus - 2;
 113       else {
 114         newstatus = (long) self;
 115         self->p_nextwaiting = (pthread_descr) oldstatus;
 116       }
 117     }
 118     while (! sem_compare_and_swap(sem, oldstatus, newstatus));
 119     if (newstatus & 1)
 120       /* We got the semaphore. */
 121       return 0;
 122     /* Wait for sem_post or cancellation */
 123     suspend_with_cancellation(self);
 124     /* This is a cancellation point */
 125     if (self->p_canceled && self->p_cancelstate == PTHREAD_CANCEL_ENABLE) {
 126       /* Remove ourselves from the waiting list if we're still on it */
 127       /* First check if we're at the head of the list. */
 128       do {
 129         oldstatus = sem->sem_status;
 130         if (oldstatus != (long) self) break;
 131         newstatus = (long) self->p_nextwaiting;
 132       }
 133       while (! sem_compare_and_swap(sem, oldstatus, newstatus));
 134       /* Now, check if we're somewhere in the list.
 135          There's a race condition with sem_post here, but it does not matter:
 136          the net result is that at the time pthread_exit is called,
 137          self is no longer reachable from sem->sem_status. */
 138       if (oldstatus != (long) self && (oldstatus & 1) == 0) {
 139         for (th = &(((pthread_descr) oldstatus)->p_nextwaiting);
 140              *th != NULL && *th != (pthread_descr) 1;
 141              th = &((*th)->p_nextwaiting)) {
 142           if (*th == self) {
 143             *th = self->p_nextwaiting;
 144             break;
 145           }
 146         }
 147       }
 148       pthread_exit(PTHREAD_CANCELED);
 149     }
 150   }
 151 }
 152
 153 int sem_trywait(sem_t * sem)
 154 {
 155   long oldstatus, newstatus;
 156
 157   do {
 158     oldstatus = sem->sem_status;
 159     if ((oldstatus & 1) == 0 || (oldstatus == 1)) {
 160       errno = EAGAIN;
 161       return -1;
 162     }
 163     newstatus = oldstatus - 2;
 164   }
 165   while (! sem_compare_and_swap(sem, oldstatus, newstatus));
 166   return 0;
 167 }
 168
 169 int sem_post(sem_t * sem)
 170 {
 171   long oldstatus, newstatus;
 172
 173   do {
 174     oldstatus = sem->sem_status;
 175     if ((oldstatus & 1) == 0)
 176       newstatus = 3;
 177     else {
 178       if (oldstatus >= SEM_VALUE_MAX) {
 179         /* Overflow */
 180         errno = ERANGE;
 181         return -1;
 182       }
 183       newstatus = oldstatus + 2;
 184     }
 185   }
 186   while (! sem_compare_and_swap(sem, oldstatus, newstatus));
 187   if ((oldstatus & 1) == 0)
 188     sem_restart_list((pthread_descr) oldstatus);
 189   return 0;
 190 }
 191
 192 int sem_getvalue(sem_t * sem, int * sval)
 193 {
 194   long status = sem->sem_status;
 195   if (status & 1)
 196     *sval = (int)((unsigned long) status >> 1);
 197   else
 198     *sval = 0;
 199   return 0;
 200 }
 201
 202 int sem_destroy(sem_t * sem)
 203 {
 204   if ((sem->sem_status & 1) == 0) {
 205     errno = EBUSY;
 206     return -1;
 207   }
 208   return 0;
 209 }
 210
 211 /* Auxiliary function for restarting all threads on a waiting list,
 212    in priority order. */
 213
 214 static void sem_restart_list(pthread_descr waiting)
 215 {
 216   pthread_descr th, towake, *p;
 217
 218   /* Sort list of waiting threads by decreasing priority (insertion sort) */
 219   towake = NULL;
 220   while (waiting != (pthread_descr) 1) {
 221     th = waiting;
 222     waiting = waiting->p_nextwaiting;
 223     p = &towake;
 224     while (*p != NULL && th->p_priority < (*p)->p_priority)
 225       p = &((*p)->p_nextwaiting);
 226     th->p_nextwaiting = *p;
 227     *p = th;
 228   }
 229   /* Wake up threads in priority order */
 230   while (towake != NULL) {
 231     th = towake;
 232     towake = towake->p_nextwaiting;
 233     th->p_nextwaiting = NULL;
 234     restart(th);
 235   }
 236 }