uspace/lib/c/generic/private/futex.h

   1 /*
   2  * Copyright (c) 2006 Jakub Jermar
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup libc
  30  * @{
  31  */
  32 /** @file
  33  */
  34
  35 #ifndef LIBC_FUTEX_H_
  36 #define LIBC_FUTEX_H_
  37
  38 #include <assert.h>
  39 #include <atomic.h>
  40 #include <errno.h>
  41 #include <libc.h>
  42 #include <time.h>
  43
  44 typedef struct futex {
  45         atomic_t val;
  46 #ifdef CONFIG_DEBUG_FUTEX
  47         void *owner;
  48 #endif
  49 } futex_t;
  50
  51 extern void futex_initialize(futex_t *futex, int value);
  52
  53 #ifdef CONFIG_DEBUG_FUTEX
  54
  55 #define FUTEX_INITIALIZE(val) {{ (val) }, NULL }
  56 #define FUTEX_INITIALIZER     FUTEX_INITIALIZE(1)
  57
  58 void __futex_assert_is_locked(futex_t *, const char *);
  59 void __futex_assert_is_not_locked(futex_t *, const char *);
  60 void __futex_lock(futex_t *, const char *);
  61 void __futex_unlock(futex_t *, const char *);
  62 bool __futex_trylock(futex_t *, const char *);
  63 void __futex_give_to(futex_t *, void *, const char *);
  64
  65 #define futex_lock(futex) __futex_lock((futex), #futex)
  66 #define futex_unlock(futex) __futex_unlock((futex), #futex)
  67 #define futex_trylock(futex) __futex_trylock((futex), #futex)
  68
  69 #define futex_give_to(futex, new_owner) __futex_give_to((futex), (new_owner), #futex)
  70 #define futex_assert_is_locked(futex) __futex_assert_is_locked((futex), #futex)
  71 #define futex_assert_is_not_locked(futex) __futex_assert_is_not_locked((futex), #futex)
  72
  73 #else
  74
  75 #define FUTEX_INITIALIZE(val) {{ (val) }}
  76 #define FUTEX_INITIALIZER     FUTEX_INITIALIZE(1)
  77
  78 #define futex_lock(fut)     (void) futex_down((fut))
  79 #define futex_trylock(fut)  futex_trydown((fut))
  80 #define futex_unlock(fut)   (void) futex_up((fut))
  81
  82 #define futex_give_to(fut, owner) ((void)0)
  83 #define futex_assert_is_locked(fut) assert((atomic_signed_t) (fut)->val.count <= 0)
  84 #define futex_assert_is_not_locked(fut) ((void)0)
  85
  86 #endif
  87
  88 /** Down the futex with timeout, composably.
  89  *
  90  * This means that when the operation fails due to a timeout or being
  91  * interrupted, the next futex_up() is ignored, which allows certain kinds of
  92  * composition of synchronization primitives.
  93  *
  94  * In most other circumstances, regular futex_down_timeout() is a better choice.
  95  *
  96  * @param futex Futex.
  97  *
  98  * @return ENOENT if there is no such virtual address.
  99  * @return ETIMEOUT if timeout expires.
 100  * @return EOK on success.
 101  * @return Error code from <errno.h> otherwise.
 102  *
 103  */
 104 static inline errno_t futex_down_composable(futex_t *futex,
 105     const struct timespec *expires)
 106 {
 107         // TODO: Add tests for this.
 108
 109         if ((atomic_signed_t) atomic_predec(&futex->val) >= 0)
 110                 return EOK;
 111
 112         usec_t timeout;
 113
 114         if (!expires) {
 115                 /* No timeout. */
 116                 timeout = 0;
 117         } else {
 118                 if (expires->tv_sec == 0) {
 119                         /* We can't just return ETIMEOUT. That wouldn't be composable. */
 120                         timeout = 1;
 121                 } else {
 122                         struct timespec tv;
 123                         getuptime(&tv);
 124                         timeout = ts_gteq(&tv, expires) ? 1 :
 125                             NSEC2USEC(ts_sub_diff(expires, &tv));
 126                 }
 127
 128                 assert(timeout > 0);
 129         }
 130
 131         return __SYSCALL2(SYS_FUTEX_SLEEP, (sysarg_t) &futex->val.count, (sysarg_t) timeout);
 132 }
 133
 134 /** Up the futex.
 135  *
 136  * @param futex Futex.
 137  *
 138  * @return ENOENT if there is no such virtual address.
 139  * @return EOK on success.
 140  * @return Error code from <errno.h> otherwise.
 141  *
 142  */
 143 static inline errno_t futex_up(futex_t *futex)
 144 {
 145         if ((atomic_signed_t) atomic_postinc(&futex->val) < 0)
 146                 return __SYSCALL1(SYS_FUTEX_WAKEUP, (sysarg_t) &futex->val.count);
 147
 148         return EOK;
 149 }
 150
 151 static inline errno_t futex_down_timeout(futex_t *futex,
 152     const struct timespec *expires)
 153 {
 154         if (expires && expires->tv_sec == 0 && expires->tv_nsec == 0) {
 155                 /* Nonblocking down. */
 156
 157                 /*
 158                  * Try good old CAS a few times.
 159                  * Not too much though, we don't want to bloat the caller.
 160                  */
 161                 for (int i = 0; i < 2; i++) {
 162                         atomic_signed_t old = atomic_get(&futex->val);
 163                         if (old <= 0)
 164                                 return ETIMEOUT;
 165
 166                         if (cas(&futex->val, old, old - 1))
 167                                 return EOK;
 168                 }
 169
 170                 // TODO: builtin atomics with relaxed ordering can make this
 171                 //       faster.
 172
 173                 /*
 174                  * If we don't succeed with CAS, we can't just return failure
 175                  * because that would lead to spurious failures where
 176                  * futex_down_timeout returns ETIMEOUT despite there being
 177                  * available tokens. That could break some algorithms.
 178                  * We also don't want to loop on CAS indefinitely, because
 179                  * that would make the semaphore not wait-free, even when all
 180                  * atomic operations and the underlying base semaphore are all
 181                  * wait-free.
 182                  * Instead, we fall back to regular down_timeout(), with
 183                  * an already expired deadline. That way we delegate all these
 184                  * concerns to the base semaphore.
 185                  */
 186         }
 187
 188         /*
 189          * This combination of a "composable" sleep followed by futex_up() on
 190          * failure is necessary to prevent breakage due to certain race
 191          * conditions.
 192          */
 193         errno_t rc = futex_down_composable(futex, expires);
 194         if (rc != EOK)
 195                 futex_up(futex);
 196         return rc;
 197 }
 198
 199 /** Try to down the futex.
 200  *
 201  * @param futex Futex.
 202  *
 203  * @return true if the futex was acquired.
 204  * @return false if the futex was not acquired.
 205  *
 206  */
 207 static inline bool futex_trydown(futex_t *futex)
 208 {
 209         /*
 210          * down_timeout with an already expired deadline should behave like
 211          * trydown.
 212          */
 213         struct timespec tv = { .tv_sec = 0, .tv_nsec = 0 };
 214         return futex_down_timeout(futex, &tv) == EOK;
 215 }
 216
 217 /** Down the futex.
 218  *
 219  * @param futex Futex.
 220  *
 221  * @return ENOENT if there is no such virtual address.
 222  * @return EOK on success.
 223  * @return Error code from <errno.h> otherwise.
 224  *
 225  */
 226 static inline errno_t futex_down(futex_t *futex)
 227 {
 228         return futex_down_timeout(futex, NULL);
 229 }
 230
 231 #endif
 232
 233 /** @}
 234  */