src/runtime/pthread-futex.c

   1 /* An approximation of Linux futexes implemented using pthread mutexes
   2  * and pthread condition variables.
   3  */
   4
   5 /*
   6  * This software is part of the SBCL system. See the README file for
   7  * more information.
   8  *
   9  * The software is in the public domain and is provided with
  10  * absolutely no warranty. See the COPYING and CREDITS files for more
  11  * information.
  12  */
  13
  14 #include "sbcl.h"
  15
  16 #if defined(LISP_FEATURE_SB_THREAD) && defined(LISP_FEATURE_SB_PTHREAD_FUTEX)
  17
  18 #include <errno.h>
  19 #include <pthread.h>
  20 #include <stdlib.h>
  21
  22 #include "runtime.h"
  23 #include "arch.h"
  24 #include "target-arch-os.h"
  25 #include "os.h"
  26
  27 #define FUTEX_WAIT_NSEC (10000000) /* 10 msec */
  28
  29 #if 1
  30 # define futex_assert(ex)                                              \
  31 do {                                                                   \
  32     if (!(ex)) futex_abort();                                          \
  33 } while (0)
  34 # define futex_assert_verbose(ex, fmt, ...)                            \
  35 do {                                                                   \
  36     if (!(ex)) {                                                       \
  37         fprintf(stderr, fmt, ## __VA_ARGS__);                          \
  38         futex_abort();                                                 \
  39     }                                                                  \
  40 } while (0)
  41 #else
  42 # define futex_assert(ex)
  43 # define futex_assert_verbose(ex, fmt, ...)
  44 #endif
  45
  46 #define futex_abort()                                                  \
  47   lose("Futex assertion failure, file \"%s\", line %d\n", __FILE__, __LINE__)
  48
  49 struct futex {
  50     struct futex *prev;
  51     struct futex *next;
  52     int *lock_word;
  53     pthread_mutex_t mutex;
  54     pthread_cond_t cond;
  55     int count;
  56 };
  57
  58 static pthread_mutex_t futex_lock = PTHREAD_MUTEX_INITIALIZER;
  59
  60 static struct futex *futex_head = NULL;
  61 static struct futex *futex_free_head = NULL;
  62
  63 static struct futex *
  64 futex_add(struct futex *head, struct futex *futex)
  65 {
  66     futex->prev = NULL;
  67     futex->next = head;
  68     if (head != NULL)
  69         head->prev = futex;
  70     head = futex;
  71
  72     return head;
  73 }
  74
  75 static struct futex *
  76 futex_delete(struct futex *head, struct futex *futex)
  77 {
  78     if (head == futex)
  79         head = futex->next;
  80     if (futex->prev != NULL)
  81         futex->prev->next = futex->next;
  82     if (futex->next != NULL)
  83         futex->next->prev = futex->prev;
  84
  85     return head;
  86 }
  87
  88 static struct futex *
  89 futex_find(struct futex *head, int *lock_word)
  90 {
  91     struct futex *futex;
  92
  93     for (futex = head; futex != NULL; futex = futex->next) {
  94         if (futex->lock_word == lock_word)
  95             break;
  96     }
  97
  98     return futex;
  99 }
 100
 101 static struct futex *
 102 futex_get(int *lock_word)
 103 {
 104     int ret;
 105     struct futex *futex;
 106
 107     ret = pthread_mutex_lock(&futex_lock);
 108     futex_assert(ret == 0);
 109
 110     futex = futex_find(futex_head, lock_word);
 111
 112     if (futex != NULL)
 113         futex->count++;
 114
 115     ret = pthread_mutex_unlock(&futex_lock);
 116     futex_assert(ret == 0);
 117
 118     if (futex != NULL) {
 119         ret = pthread_mutex_lock(&futex->mutex);
 120         futex_assert(ret == 0);
 121     }
 122
 123     return futex;
 124 }
 125
 126 static struct futex *
 127 futex_allocate(int *lock_word)
 128 {
 129     int ret;
 130     struct futex *futex;
 131
 132     ret = pthread_mutex_lock(&futex_lock);
 133     futex_assert(ret == 0);
 134
 135     futex = futex_free_head;
 136
 137     if (futex != NULL)
 138         futex_free_head = futex_delete(futex_free_head, futex);
 139
 140     ret = pthread_mutex_unlock(&futex_lock);
 141     futex_assert(ret == 0);
 142
 143     if (futex == NULL) {
 144         futex = malloc(sizeof(struct futex));
 145         futex_assert(futex != NULL);
 146
 147         ret = pthread_mutex_init(&futex->mutex, NULL);
 148         futex_assert(ret == 0);
 149
 150         ret = pthread_cond_init(&futex->cond, NULL);
 151         futex_assert(ret == 0);
 152     }
 153
 154     futex->lock_word = lock_word;
 155     futex->count = 1;
 156
 157     /* Lock mutex before register to avoid race conditions. */
 158     ret = pthread_mutex_lock(&futex->mutex);
 159     futex_assert(ret == 0);
 160
 161     ret = pthread_mutex_lock(&futex_lock);
 162     futex_assert(ret == 0);
 163
 164     futex_head = futex_add(futex_head, futex);
 165
 166     ret = pthread_mutex_unlock(&futex_lock);
 167     futex_assert(ret == 0);
 168
 169     return futex;
 170 }
 171
 172 static void
 173 futex_cleanup(void *p)
 174 {
 175     struct futex *futex = (struct futex *)p;
 176     int ret, count;
 177
 178     ret = pthread_mutex_lock(&futex_lock);
 179     futex_assert(ret == 0);
 180
 181     count = --futex->count;
 182     if (count <= 0) {
 183         futex_head = futex_delete(futex_head, futex);
 184         futex_free_head = futex_add(futex_free_head, futex);
 185     }
 186
 187     ret = pthread_mutex_unlock(&futex_lock);
 188     futex_assert(ret == 0);
 189
 190     ret = pthread_mutex_unlock(&futex->mutex);
 191     futex_assert(ret == 0);
 192 }
 193
 194 static int
 195 futex_relative_to_abs(struct timespec *tp, int relative)
 196 {
 197     int ret;
 198     struct timeval tv;
 199
 200     ret = gettimeofday(&tv, NULL);
 201     if (ret != 0)
 202         return ret;
 203     tp->tv_sec = tv.tv_sec + (tv.tv_usec * 1000 + relative) / 1000000000;
 204     tp->tv_nsec = (tv.tv_usec * 1000 + relative) % 1000000000;
 205     return 0;
 206 }
 207
 208 int
 209 futex_wait(int *lock_word, int oldval)
 210 {
 211     int ret, result;
 212     struct futex *futex;
 213     sigset_t oldset, newset;
 214
 215     sigemptyset(&newset);
 216     sigaddset_deferrable(&newset);
 217
 218 again:
 219     pthread_sigmask(SIG_BLOCK, &newset, &oldset);
 220
 221     futex = futex_get(lock_word);
 222
 223     if (futex == NULL)
 224         futex = futex_allocate(lock_word);
 225
 226     pthread_cleanup_push(futex_cleanup, futex);
 227
 228     /* Compare lock_word after the lock is aquired to avoid race
 229      * conditions. */
 230     if (*(volatile int *)lock_word != oldval) {
 231         result = EWOULDBLOCK;
 232         goto done;
 233     }
 234
 235     /* It's not possible to unwind frames across pthread_cond_wait(3). */
 236     for (;;) {
 237         int i;
 238         sigset_t pendset;
 239         struct timespec abstime;
 240
 241         ret = futex_relative_to_abs(&abstime, FUTEX_WAIT_NSEC);
 242         futex_assert(ret == 0);
 243
 244         result = pthread_cond_timedwait(&futex->cond, &futex->mutex,
 245                                         &abstime);
 246         futex_assert(result == 0 || result == ETIMEDOUT);
 247
 248         if (result != ETIMEDOUT)
 249             break;
 250
 251         /* futex system call of Linux returns with EINTR errno when
 252          * it's interrupted by signals.  Check pending signals here to
 253          * emulate this behaviour. */
 254         sigpending(&pendset);
 255         for (i = 1; i < NSIG; i++) {
 256             if (sigismember(&pendset, i) && sigismember(&newset, i)) {
 257                 result = EINTR;
 258                 goto done;
 259             }
 260         }
 261     }
 262 done:
 263     ; /* Null statement is required between label and pthread_cleanup_pop. */
 264     pthread_cleanup_pop(1);
 265     pthread_sigmask(SIG_SETMASK, &oldset, NULL);
 266
 267     /* futex_wake() in linux-os.c loops when futex system call returns
 268      * EINTR.  */
 269     if (result == EINTR) {
 270         sched_yield();
 271         goto again;
 272     }
 273
 274     return result;
 275 }
 276
 277 int
 278 futex_wake(int *lock_word, int n)
 279 {
 280     int ret;
 281     struct futex *futex;
 282     sigset_t newset, oldset;
 283
 284     sigemptyset(&newset);
 285     sigaddset_deferrable(&newset);
 286
 287     pthread_sigmask(SIG_BLOCK, &newset, &oldset);
 288
 289     futex = futex_get(lock_word);
 290
 291     if (futex != NULL) {
 292         pthread_cleanup_push(futex_cleanup, futex);
 293
 294         /* The lisp-side code passes N=2**29-1 for a broadcast. */
 295         if (n >= ((1 << 29) - 1)) {
 296             /* CONDITION-BROADCAST */
 297             ret = pthread_cond_broadcast(&futex->cond);
 298             futex_assert(ret == 0);
 299         } else {
 300             while (n-- > 0) {
 301                 ret = pthread_cond_signal(&futex->cond);
 302                 futex_assert(ret == 0);
 303             }
 304         }
 305
 306         pthread_cleanup_pop(1);
 307     }
 308
 309     pthread_sigmask(SIG_SETMASK, &oldset, NULL);
 310
 311     return 0;
 312 }
 313 #endif