1 /* Low-level lock implementation. Generic futex-based version. 2 Copyright (C) 2005-2022 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 <https://www.gnu.org/licenses/>. */ 18 19 #ifndef _LOWLEVELLOCK_H 20 #define _LOWLEVELLOCK_H 1 21 22 #include <atomic.h> 23 #include <elision-conf.h> 24 #include <lowlevellock-futex.h> 25 #include <time.h> 26 27 /* Low-level locks use a combination of atomic operations (to acquire and 28 release lock ownership) and futex operations (to block until the state 29 of a lock changes). A lock can be in one of three states: 30 0: not acquired, 31 1: acquired with no waiters; no other threads are blocked or about to block 32 for changes to the lock state, 33 >1: acquired, possibly with waiters; there may be other threads blocked or 34 about to block for changes to the lock state. 35 36 We expect that the common case is an uncontended lock, so we just need 37 to transition the lock between states 0 and 1; releasing the lock does 38 not need to wake any other blocked threads. If the lock is contended 39 and a thread decides to block using a futex operation, then this thread 40 needs to first change the state to >1; if this state is observed during 41 lock release, the releasing thread will wake one of the potentially 42 blocked threads. 43 44 Much of this code takes a 'private' parameter. This may be: 45 LLL_PRIVATE: lock only shared within a process 46 LLL_SHARED: lock may be shared across processes. 47 48 Condition variables contain an optimization for broadcasts that requeues 49 waiting threads on a lock's futex. Therefore, there is a special 50 variant of the locks (whose name contains "cond") that makes sure to 51 always set the lock state to >1 and not just 1. 52 53 Robust locks set the lock to the id of the owner. This allows detection 54 of the case where the owner exits without releasing the lock. Flags are 55 OR'd with the owner id to record additional information about lock state. 56 Therefore the states of robust locks are: 57 0: not acquired 58 id: acquired (by user identified by id & FUTEX_TID_MASK) 59 60 The following flags may be set in the robust lock value: 61 FUTEX_WAITERS - possibly has waiters 62 FUTEX_OWNER_DIED - owning user has exited without releasing the futex. */ 63 64 65 /* If LOCK is 0 (not acquired), set to 1 (acquired with no waiters) and return 66 0. Otherwise leave lock unchanged and return non-zero to indicate that the 67 lock was not acquired. */ 68 #define __lll_trylock(lock) \ 69 __glibc_unlikely (atomic_compare_and_exchange_bool_acq ((lock), 1, 0)) 70 #define lll_trylock(lock) \ 71 __lll_trylock (&(lock)) 72 73 /* If LOCK is 0 (not acquired), set to 2 (acquired, possibly with waiters) and 74 return 0. Otherwise leave lock unchanged and return non-zero to indicate 75 that the lock was not acquired. */ 76 #define lll_cond_trylock(lock) \ 77 __glibc_unlikely (atomic_compare_and_exchange_bool_acq (&(lock), 2, 0)) 78 79 extern void __lll_lock_wait_private (int *futex); 80 libc_hidden_proto (__lll_lock_wait_private) 81 extern void __lll_lock_wait (int *futex, int private); 82 libc_hidden_proto (__lll_lock_wait) 83 84 /* This is an expression rather than a statement even though its value is 85 void, so that it can be used in a comma expression or as an expression 86 that's cast to void. */ 87 /* The inner conditional compiles to a call to __lll_lock_wait_private if 88 private is known at compile time to be LLL_PRIVATE, and to a call to 89 __lll_lock_wait otherwise. */ 90 /* If FUTEX is 0 (not acquired), set to 1 (acquired with no waiters) and 91 return. Otherwise, ensure that it is >1 (acquired, possibly with waiters) 92 and then block until we acquire the lock, at which point FUTEX will still be 93 >1. The lock is always acquired on return. */ 94 #define __lll_lock(futex, private) \ 95 ((void) \ 96 ({ \ 97 int *__futex = (futex); \ 98 if (__glibc_unlikely \ 99 (atomic_compare_and_exchange_bool_acq (__futex, 1, 0))) \ 100 { \ 101 if (__builtin_constant_p (private) && (private) == LLL_PRIVATE) \ 102 __lll_lock_wait_private (__futex); \ 103 else \ 104 __lll_lock_wait (__futex, private); \ 105 } \ 106 })) 107 #define lll_lock(futex, private) \ 108 __lll_lock (&(futex), private) 109 110 111 /* This is an expression rather than a statement even though its value is 112 void, so that it can be used in a comma expression or as an expression 113 that's cast to void. */ 114 /* Unconditionally set FUTEX to 2 (acquired, possibly with waiters). If FUTEX 115 was 0 (not acquired) then return. Otherwise, block until the lock is 116 acquired, at which point FUTEX is 2 (acquired, possibly with waiters). The 117 lock is always acquired on return. */ 118 #define __lll_cond_lock(futex, private) \ 119 ((void) \ 120 ({ \ 121 int *__futex = (futex); \ 122 if (__glibc_unlikely (atomic_exchange_acq (__futex, 2) != 0)) \ 123 __lll_lock_wait (__futex, private); \ 124 })) 125 #define lll_cond_lock(futex, private) __lll_cond_lock (&(futex), private) 126 127 128 extern void __lll_lock_wake_private (int *futex); 129 libc_hidden_proto (__lll_lock_wake_private) 130 extern void __lll_lock_wake (int *futex, int private); 131 libc_hidden_proto (__lll_lock_wake) 132 133 /* This is an expression rather than a statement even though its value is 134 void, so that it can be used in a comma expression or as an expression 135 that's cast to void. */ 136 /* Unconditionally set FUTEX to 0 (not acquired), releasing the lock. If FUTEX 137 was >1 (acquired, possibly with waiters), then wake any waiters. The waiter 138 that acquires the lock will set FUTEX to >1. 139 Evaluate PRIVATE before releasing the lock so that we do not violate the 140 mutex destruction requirements. Specifically, we need to ensure that 141 another thread can destroy the mutex (and reuse its memory) once it 142 acquires the lock and when there will be no further lock acquisitions; 143 thus, we must not access the lock after releasing it, or those accesses 144 could be concurrent with mutex destruction or reuse of the memory. */ 145 #define __lll_unlock(futex, private) \ 146 ((void) \ 147 ({ \ 148 int *__futex = (futex); \ 149 int __private = (private); \ 150 int __oldval = atomic_exchange_rel (__futex, 0); \ 151 if (__glibc_unlikely (__oldval > 1)) \ 152 { \ 153 if (__builtin_constant_p (private) && (private) == LLL_PRIVATE) \ 154 __lll_lock_wake_private (__futex); \ 155 else \ 156 __lll_lock_wake (__futex, __private); \ 157 } \ 158 })) 159 #define lll_unlock(futex, private) \ 160 __lll_unlock (&(futex), private) 161 162 163 #define lll_islocked(futex) \ 164 ((futex) != LLL_LOCK_INITIALIZER) 165 166 167 /* Our internal lock implementation is identical to the binary-compatible 168 mutex implementation. */ 169 170 /* Initializers for lock. */ 171 #define LLL_LOCK_INITIALIZER (0) 172 #define LLL_LOCK_INITIALIZER_LOCKED (1) 173 174 /* Elision support. */ 175 176 #if ENABLE_ELISION_SUPPORT 177 /* Force elision for all new locks. This is used to decide whether 178 existing DEFAULT locks should be automatically upgraded to elision 179 in pthread_mutex_lock. Disabled for suid programs. Only used when 180 elision is available. */ 181 extern int __pthread_force_elision; 182 libc_hidden_proto (__pthread_force_elision) 183 184 extern void __lll_elision_init (void) attribute_hidden; 185 extern int __lll_clocklock_elision (int *futex, short *adapt_count, 186 clockid_t clockid, 187 const struct __timespec64 *timeout, 188 int private); 189 libc_hidden_proto (__lll_clocklock_elision) 190 191 extern int __lll_lock_elision (int *futex, short *adapt_count, int private); 192 libc_hidden_proto (__lll_lock_elision) 193 194 # if ELISION_UNLOCK_NEEDS_ADAPT_COUNT 195 extern int __lll_unlock_elision (int *lock, short *adapt_count, int private); 196 # else 197 extern int __lll_unlock_elision (int *lock, int private); 198 # endif 199 libc_hidden_proto (__lll_unlock_elision) 200 201 extern int __lll_trylock_elision (int *lock, short *adapt_count); 202 libc_hidden_proto (__lll_trylock_elision) 203 204 # define lll_clocklock_elision(futex, adapt_count, clockid, timeout, private) \ 205 __lll_clocklock_elision (&(futex), &(adapt_count), clockid, timeout, private) 206 # define lll_lock_elision(futex, adapt_count, private) \ 207 __lll_lock_elision (&(futex), &(adapt_count), private) 208 # define lll_trylock_elision(futex, adapt_count) \ 209 __lll_trylock_elision (&(futex), &(adapt_count)) 210 # if ELISION_UNLOCK_NEEDS_ADAPT_COUNT 211 # define lll_unlock_elision(futex, adapt_count, private) \ 212 __lll_unlock_elision (&(futex), &(adapt_count), private) 213 # else 214 # define lll_unlock_elision(futex, adapt_count, private) \ 215 __lll_unlock_elision (&(futex), private) 216 # endif 217 218 /* Automatically enable elision for existing user lock kinds. */ 219 # define FORCE_ELISION(m, s) \ 220 if (__pthread_force_elision) \ 221 { \ 222 /* See concurrency notes regarding __kind in \ 223 struct __pthread_mutex_s in \ 224 sysdeps/nptl/bits/thread-shared-types.h. \ 225 \ 226 There are the following cases for the kind of a mutex \ 227 (The mask PTHREAD_MUTEX_ELISION_FLAGS_NP covers the flags \ 228 PTHREAD_MUTEX_ELISION_NP and PTHREAD_MUTEX_NO_ELISION_NP where \ 229 only one of both flags can be set): \ 230 - both flags are not set: \ 231 This is the first lock operation for this mutex. Enable \ 232 elision as it is not enabled so far. \ 233 Note: It can happen that multiple threads are calling e.g. \ 234 pthread_mutex_lock at the same time as the first lock \ 235 operation for this mutex. Then elision is enabled for this \ 236 mutex by multiple threads. Storing with relaxed MO is enough \ 237 as all threads will store the same new value for the kind of \ 238 the mutex. But we have to ensure that we always use the \ 239 elision path regardless if this thread has enabled elision or \ 240 another one. \ 241 \ 242 - PTHREAD_MUTEX_ELISION_NP flag is set: \ 243 Elision was already enabled for this mutex by a previous lock \ 244 operation. See case above. Just use the elision path. \ 245 \ 246 - PTHREAD_MUTEX_NO_ELISION_NP flag is set: \ 247 Elision was explicitly disabled by pthread_mutexattr_settype. \ 248 Do not use the elision path. \ 249 Note: The flag PTHREAD_MUTEX_NO_ELISION_NP will never be \ 250 changed after mutex initialization. */ \ 251 int mutex_kind = atomic_load_relaxed (&((m)->__data.__kind)); \ 252 if ((mutex_kind & PTHREAD_MUTEX_ELISION_FLAGS_NP) == 0) \ 253 { \ 254 mutex_kind |= PTHREAD_MUTEX_ELISION_NP; \ 255 atomic_store_relaxed (&((m)->__data.__kind), mutex_kind); \ 256 } \ 257 if ((mutex_kind & PTHREAD_MUTEX_ELISION_NP) != 0) \ 258 { \ 259 s; \ 260 } \ 261 } 262 263 #else /* !ENABLE_ELISION_SUPPORT */ 264 265 # define lll_clocklock_elision(futex, adapt_count, clockid, abstime, private) \ 266 __futex_clocklock64 (&(futex), clockid, abstime, private) 267 # define lll_lock_elision(lock, try_lock, private) \ 268 ({ lll_lock (lock, private); 0; }) 269 # define lll_trylock_elision(a,t) lll_trylock(a) 270 # define lll_unlock_elision(a,b,c) ({ lll_unlock (a,c); 0; }) 271 # define FORCE_ELISION(m, s) 272 273 #endif /* !ENABLE_ELISION_SUPPORT */ 274 275 #endif /* lowlevellock.h */ 276