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