sysdeps/nptl/lowlevellock.h

   1 /* Low-level lock implementation.  Generic futex-based version.
   2    Copyright (C) 2005-2016 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library 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 GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library.  If not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #ifndef _LOWLEVELLOCK_H
  20 #define _LOWLEVELLOCK_H 1
  21
  22 #include <atomic.h>
  23 #include <lowlevellock-futex.h>
  24
  25 /* Low-level locks use a combination of atomic operations (to acquire and
  26    release lock ownership) and futex operations (to block until the state
  27    of a lock changes).  A lock can be in one of three states:
  28    0:  not acquired,
  29    1:  acquired with no waiters; no other threads are blocked or about to block
  30        for changes to the lock state,
  31    >1: acquired, possibly with waiters; there may be other threads blocked or
  32        about to block for changes to the lock state.
  33
  34    We expect that the common case is an uncontended lock, so we just need
  35    to transition the lock between states 0 and 1; releasing the lock does
  36    not need to wake any other blocked threads.  If the lock is contended
  37    and a thread decides to block using a futex operation, then this thread
  38    needs to first change the state to >1; if this state is observed during
  39    lock release, the releasing thread will wake one of the potentially
  40    blocked threads.
  41
  42    Much of this code takes a 'private' parameter.  This may be:
  43    LLL_PRIVATE: lock only shared within a process
  44    LLL_SHARED:  lock may be shared across processes.
  45
  46    Condition variables contain an optimization for broadcasts that requeues
  47    waiting threads on a lock's futex.  Therefore, there is a special
  48    variant of the locks (whose name contains "cond") that makes sure to
  49    always set the lock state to >1 and not just 1.
  50
  51    Robust locks set the lock to the id of the owner.  This allows detection
  52    of the case where the owner exits without releasing the lock.  Flags are
  53    OR'd with the owner id to record additional information about lock state.
  54    Therefore the states of robust locks are:
  55     0: not acquired
  56    id: acquired (by user identified by id & FUTEX_TID_MASK)
  57
  58    The following flags may be set in the robust lock value:
  59    FUTEX_WAITERS     - possibly has waiters
  60    FUTEX_OWNER_DIED  - owning user has exited without releasing the futex.  */
  61
  62
  63 /* If LOCK is 0 (not acquired), set to 1 (acquired with no waiters) and return
  64    0.  Otherwise leave lock unchanged and return non-zero to indicate that the
  65    lock was not acquired.  */
  66 #define lll_trylock(lock)       \
  67   atomic_compare_and_exchange_bool_acq (&(lock), 1, 0)
  68
  69 /* If LOCK is 0 (not acquired), set to 2 (acquired, possibly with waiters) and
  70    return 0.  Otherwise leave lock unchanged and return non-zero to indicate
  71    that the lock was not acquired.  */
  72 #define lll_cond_trylock(lock)  \
  73   atomic_compare_and_exchange_bool_acq (&(lock), 2, 0)
  74
  75 extern void __lll_lock_wait_private (int *futex) attribute_hidden;
  76 extern void __lll_lock_wait (int *futex, int private) attribute_hidden;
  77 extern int __lll_robust_lock_wait (int *futex, int private) attribute_hidden;
  78
  79 /* This is an expression rather than a statement even though its value is
  80    void, so that it can be used in a comma expression or as an expression
  81    that's cast to void.  */
  82 /* The inner conditional compiles to a call to __lll_lock_wait_private if
  83    private is known at compile time to be LLL_PRIVATE, and to a call to
  84    __lll_lock_wait otherwise.  */
  85 /* If FUTEX is 0 (not acquired), set to 1 (acquired with no waiters) and
  86    return.  Otherwise, ensure that it is >1 (acquired, possibly with waiters)
  87    and then block until we acquire the lock, at which point FUTEX will still be
  88    >1.  The lock is always acquired on return.  */
  89 #define __lll_lock(futex, private)                                      \
  90   ((void)                                                               \
  91    ({                                                                   \
  92      int *__futex = (futex);                                            \
  93      if (__glibc_unlikely                                               \
  94          (atomic_compare_and_exchange_bool_acq (__futex, 1, 0)))        \
  95        {                                                                \
  96          if (__builtin_constant_p (private) && (private) == LLL_PRIVATE) \
  97            __lll_lock_wait_private (__futex);                           \
  98          else                                                           \
  99            __lll_lock_wait (__futex, private);                          \
 100        }                                                                \
 101    }))
 102 #define lll_lock(futex, private)        \
 103   __lll_lock (&(futex), private)
 104
 105
 106 /* If FUTEX is 0 (not acquired), set to ID (acquired with no waiters) and
 107    return 0.  Otherwise, ensure that it is set to FUTEX | FUTEX_WAITERS
 108    (acquired, possibly with waiters) and block until we acquire the lock.
 109    FUTEX will now be ID | FUTEX_WAITERS and we return 0.
 110    If the previous owner of the lock dies before we acquire the lock then FUTEX
 111    will be the value of id as set by the previous owner, with FUTEX_OWNER_DIED
 112    set (FUTEX_WAITERS may or may not be set).  We return this value to indicate
 113    that the lock is not acquired.  */
 114 #define __lll_robust_lock(futex, id, private)                           \
 115   ({                                                                    \
 116     int *__futex = (futex);                                             \
 117     int __val = 0;                                                      \
 118                                                                         \
 119     if (__glibc_unlikely                                                \
 120         (atomic_compare_and_exchange_bool_acq (__futex, id, 0)))        \
 121       __val = __lll_robust_lock_wait (__futex, private);                \
 122     __val;                                                              \
 123   })
 124 #define lll_robust_lock(futex, id, private)     \
 125   __lll_robust_lock (&(futex), id, private)
 126
 127
 128 /* This is an expression rather than a statement even though its value is
 129    void, so that it can be used in a comma expression or as an expression
 130    that's cast to void.  */
 131 /* Unconditionally set FUTEX to 2 (acquired, possibly with waiters).  If FUTEX
 132    was 0 (not acquired) then return.  Otherwise, block until the lock is
 133    acquired, at which point FUTEX is 2 (acquired, possibly with waiters).  The
 134    lock is always acquired on return.  */
 135 #define __lll_cond_lock(futex, private)                                 \
 136   ((void)                                                               \
 137    ({                                                                   \
 138      int *__futex = (futex);                                            \
 139      if (__glibc_unlikely (atomic_exchange_acq (__futex, 2) != 0))      \
 140        __lll_lock_wait (__futex, private);                              \
 141    }))
 142 #define lll_cond_lock(futex, private) __lll_cond_lock (&(futex), private)
 143
 144
 145 /* As __lll_robust_lock, but set to ID | FUTEX_WAITERS (acquired, possibly with
 146    waiters) if FUTEX is 0.  */
 147 #define lll_robust_cond_lock(futex, id, private)        \
 148   __lll_robust_lock (&(futex), (id) | FUTEX_WAITERS, private)
 149
 150
 151 extern int __lll_timedlock_wait (int *futex, const struct timespec *,
 152                                  int private) attribute_hidden;
 153 extern int __lll_robust_timedlock_wait (int *futex, const struct timespec *,
 154                                         int private) attribute_hidden;
 155
 156
 157 /* As __lll_lock, but with a timeout.  If the timeout occurs then return
 158    ETIMEDOUT.  If ABSTIME is invalid, return EINVAL.  */
 159 #define __lll_timedlock(futex, abstime, private)                \
 160   ({                                                            \
 161     int *__futex = (futex);                                     \
 162     int __val = 0;                                              \
 163                                                                 \
 164     if (__glibc_unlikely                                        \
 165         (atomic_compare_and_exchange_bool_acq (__futex, 1, 0))) \
 166       __val = __lll_timedlock_wait (__futex, abstime, private); \
 167     __val;                                                      \
 168   })
 169 #define lll_timedlock(futex, abstime, private)  \
 170   __lll_timedlock (&(futex), abstime, private)
 171
 172
 173 /* As __lll_robust_lock, but with a timeout.  If the timeout occurs then return
 174    ETIMEDOUT.  If ABSTIME is invalid, return EINVAL.  */
 175 #define __lll_robust_timedlock(futex, abstime, id, private)             \
 176   ({                                                                    \
 177     int *__futex = (futex);                                             \
 178     int __val = 0;                                                      \
 179                                                                         \
 180     if (__glibc_unlikely                                                \
 181         (atomic_compare_and_exchange_bool_acq (__futex, id, 0)))        \
 182       __val = __lll_robust_timedlock_wait (__futex, abstime, private);  \
 183     __val;                                                              \
 184   })
 185 #define lll_robust_timedlock(futex, abstime, id, private)       \
 186   __lll_robust_timedlock (&(futex), abstime, id, private)
 187
 188
 189 /* This is an expression rather than a statement even though its value is
 190    void, so that it can be used in a comma expression or as an expression
 191    that's cast to void.  */
 192 /* Unconditionally set FUTEX to 0 (not acquired), releasing the lock.  If FUTEX
 193    was >1 (acquired, possibly with waiters), then wake any waiters.  The waiter
 194    that acquires the lock will set FUTEX to >1.
 195    Evaluate PRIVATE before releasing the lock so that we do not violate the
 196    mutex destruction requirements.  Specifically, we need to ensure that
 197    another thread can destroy the mutex (and reuse its memory) once it
 198    acquires the lock and when there will be no further lock acquisitions;
 199    thus, we must not access the lock after releasing it, or those accesses
 200    could be concurrent with mutex destruction or reuse of the memory.  */
 201 #define __lll_unlock(futex, private)                    \
 202   ((void)                                               \
 203    ({                                                   \
 204      int *__futex = (futex);                            \
 205      int __private = (private);                         \
 206      int __oldval = atomic_exchange_rel (__futex, 0);   \
 207      if (__glibc_unlikely (__oldval > 1))               \
 208        lll_futex_wake (__futex, 1, __private);          \
 209    }))
 210 #define lll_unlock(futex, private)      \
 211   __lll_unlock (&(futex), private)
 212
 213
 214 /* This is an expression rather than a statement even though its value is
 215    void, so that it can be used in a comma expression or as an expression
 216    that's cast to void.  */
 217 /* Unconditionally set FUTEX to 0 (not acquired), releasing the lock.  If FUTEX
 218    had FUTEX_WAITERS set then wake any waiters.  The waiter that acquires the
 219    lock will set FUTEX_WAITERS.
 220    Evaluate PRIVATE before releasing the lock so that we do not violate the
 221    mutex destruction requirements (see __lll_unlock).  */
 222 #define __lll_robust_unlock(futex, private)             \
 223   ((void)                                               \
 224    ({                                                   \
 225      int *__futex = (futex);                            \
 226      int __private = (private);                         \
 227      int __oldval = atomic_exchange_rel (__futex, 0);   \
 228      if (__glibc_unlikely (__oldval & FUTEX_WAITERS))   \
 229        lll_futex_wake (__futex, 1, __private);          \
 230    }))
 231 #define lll_robust_unlock(futex, private)       \
 232   __lll_robust_unlock (&(futex), private)
 233
 234
 235 #define lll_islocked(futex) \
 236   ((futex) != LLL_LOCK_INITIALIZER)
 237
 238
 239 /* Our internal lock implementation is identical to the binary-compatible
 240    mutex implementation. */
 241
 242 /* Initializers for lock.  */
 243 #define LLL_LOCK_INITIALIZER            (0)
 244 #define LLL_LOCK_INITIALIZER_LOCKED     (1)
 245
 246
 247 /* The kernel notifies a process which uses CLONE_CHILD_CLEARTID via futex
 248    wake-up when the clone terminates.  The memory location contains the
 249    thread ID while the clone is running and is reset to zero by the kernel
 250    afterwards.  The kernel up to version 3.16.3 does not use the private futex
 251    operations for futex wake-up when the clone terminates.  */
 252 #define lll_wait_tid(tid) \
 253   do {                                  \
 254     __typeof (tid) __tid;               \
 255     while ((__tid = (tid)) != 0)        \
 256       lll_futex_wait (&(tid), __tid, LLL_SHARED);\
 257   } while (0)
 258
 259 extern int __lll_timedwait_tid (int *, const struct timespec *)
 260      attribute_hidden;
 261
 262 /* As lll_wait_tid, but with a timeout.  If the timeout occurs then return
 263    ETIMEDOUT.  If ABSTIME is invalid, return EINVAL.  */
 264 #define lll_timedwait_tid(tid, abstime) \
 265   ({                                                    \
 266     int __res = 0;                                      \
 267     if ((tid) != 0)                                     \
 268       __res = __lll_timedwait_tid (&(tid), (abstime));  \
 269     __res;                                              \
 270   })
 271
 272
 273 #endif  /* lowlevellock.h */