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 static int
 209 futex_istimeout(struct timeval *timeout)
 210 {
 211     int ret;
 212     struct timeval tv;
 213
 214     if (timeout == NULL)
 215         return 0;
 216
 217     ret = gettimeofday(&tv, NULL);
 218     if (ret != 0)
 219         return ret;
 220
 221     return (tv.tv_sec > timeout->tv_sec) ||
 222         ((tv.tv_sec == timeout->tv_sec) && tv.tv_usec > timeout->tv_usec);
 223 }
 224
 225 int
 226 futex_wait(int *lock_word, int oldval, long sec, unsigned long usec)
 227 {
 228     int ret, result;
 229     struct futex *futex;
 230     sigset_t oldset, newset;
 231     struct timeval tv, *timeout;
 232
 233     sigemptyset(&newset);
 234     sigaddset_deferrable(&newset);
 235
 236 again:
 237     if (sec < 0)
 238         timeout = NULL;
 239     else {
 240         ret = gettimeofday(&tv, NULL);
 241         if (ret != 0)
 242             return ret;
 243         tv.tv_sec = tv.tv_sec + sec + (tv.tv_usec + usec) / 1000000;
 244         tv.tv_usec = (tv.tv_usec + usec) % 1000000;
 245         timeout = &tv;
 246     }
 247
 248     pthread_sigmask(SIG_BLOCK, &newset, &oldset);
 249
 250     futex = futex_get(lock_word);
 251
 252     if (futex == NULL)
 253         futex = futex_allocate(lock_word);
 254
 255     pthread_cleanup_push(futex_cleanup, futex);
 256
 257     /* Compare lock_word after the lock is aquired to avoid race
 258      * conditions. */
 259     if (*(volatile int *)lock_word != oldval) {
 260         result = EWOULDBLOCK;
 261         goto done;
 262     }
 263
 264     /* It's not possible to unwind frames across pthread_cond_wait(3). */
 265     for (;;) {
 266         int i;
 267         sigset_t pendset;
 268         struct timespec abstime;
 269
 270         ret = futex_relative_to_abs(&abstime, FUTEX_WAIT_NSEC);
 271         futex_assert(ret == 0);
 272
 273         result = pthread_cond_timedwait(&futex->cond, &futex->mutex,
 274                                         &abstime);
 275         futex_assert(result == 0 || result == ETIMEDOUT);
 276
 277         if (result != ETIMEDOUT || futex_istimeout(timeout))
 278             break;
 279
 280         /* futex system call of Linux returns with EINTR errno when
 281          * it's interrupted by signals.  Check pending signals here to
 282          * emulate this behaviour. */
 283         sigpending(&pendset);
 284         for (i = 1; i < NSIG; i++) {
 285             if (sigismember(&pendset, i) && sigismember(&newset, i)) {
 286                 result = EINTR;
 287                 goto done;
 288             }
 289         }
 290     }
 291 done:
 292     ; /* Null statement is required between label and pthread_cleanup_pop. */
 293     pthread_cleanup_pop(1);
 294     pthread_sigmask(SIG_SETMASK, &oldset, NULL);
 295
 296     /* futex_wake() in linux-os.c loops when futex system call returns
 297      * EINTR.  */
 298     if (result == EINTR) {
 299         sched_yield();
 300         goto again;
 301     }
 302
 303     if (result == ETIMEDOUT)
 304         return 1;
 305
 306     return result;
 307 }
 308
 309 int
 310 futex_wake(int *lock_word, int n)
 311 {
 312     int ret;
 313     struct futex *futex;
 314     sigset_t newset, oldset;
 315
 316     sigemptyset(&newset);
 317     sigaddset_deferrable(&newset);
 318
 319     pthread_sigmask(SIG_BLOCK, &newset, &oldset);
 320
 321     futex = futex_get(lock_word);
 322
 323     if (futex != NULL) {
 324         pthread_cleanup_push(futex_cleanup, futex);
 325
 326         /* The lisp-side code passes N=2**29-1 for a broadcast. */
 327         if (n >= ((1 << 29) - 1)) {
 328             /* CONDITION-BROADCAST */
 329             ret = pthread_cond_broadcast(&futex->cond);
 330             futex_assert(ret == 0);
 331         } else {
 332             while (n-- > 0) {
 333                 ret = pthread_cond_signal(&futex->cond);
 334                 futex_assert(ret == 0);
 335             }
 336         }
 337
 338         pthread_cleanup_pop(1);
 339     }
 340
 341     pthread_sigmask(SIG_SETMASK, &oldset, NULL);
 342
 343     return 0;
 344 }
 345 #endif