1 | /* Low-level lock implementation. Generic futex-based version. |
2 | Copyright (C) 2005-2019 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 | __glibc_unlikely (atomic_compare_and_exchange_bool_acq ((lock), 1, 0)) |
68 | #define lll_trylock(lock) \ |
69 | __lll_trylock (&(lock)) |
70 | |
71 | /* If LOCK is 0 (not acquired), set to 2 (acquired, possibly with waiters) and |
72 | return 0. Otherwise leave lock unchanged and return non-zero to indicate |
73 | that the lock was not acquired. */ |
74 | #define lll_cond_trylock(lock) \ |
75 | __glibc_unlikely (atomic_compare_and_exchange_bool_acq (&(lock), 2, 0)) |
76 | |
77 | extern void __lll_lock_wait_private (int *futex) attribute_hidden; |
78 | extern void __lll_lock_wait (int *futex, int private) attribute_hidden; |
79 | |
80 | /* This is an expression rather than a statement even though its value is |
81 | void, so that it can be used in a comma expression or as an expression |
82 | that's cast to void. */ |
83 | /* The inner conditional compiles to a call to __lll_lock_wait_private if |
84 | private is known at compile time to be LLL_PRIVATE, and to a call to |
85 | __lll_lock_wait otherwise. */ |
86 | /* If FUTEX is 0 (not acquired), set to 1 (acquired with no waiters) and |
87 | return. Otherwise, ensure that it is >1 (acquired, possibly with waiters) |
88 | and then block until we acquire the lock, at which point FUTEX will still be |
89 | >1. The lock is always acquired on return. */ |
90 | #define __lll_lock(futex, private) \ |
91 | ((void) \ |
92 | ({ \ |
93 | int *__futex = (futex); \ |
94 | if (__glibc_unlikely \ |
95 | (atomic_compare_and_exchange_bool_acq (__futex, 1, 0))) \ |
96 | { \ |
97 | if (__builtin_constant_p (private) && (private) == LLL_PRIVATE) \ |
98 | __lll_lock_wait_private (__futex); \ |
99 | else \ |
100 | __lll_lock_wait (__futex, private); \ |
101 | } \ |
102 | })) |
103 | #define lll_lock(futex, private) \ |
104 | __lll_lock (&(futex), private) |
105 | |
106 | |
107 | /* This is an expression rather than a statement even though its value is |
108 | void, so that it can be used in a comma expression or as an expression |
109 | that's cast to void. */ |
110 | /* Unconditionally set FUTEX to 2 (acquired, possibly with waiters). If FUTEX |
111 | was 0 (not acquired) then return. Otherwise, block until the lock is |
112 | acquired, at which point FUTEX is 2 (acquired, possibly with waiters). The |
113 | lock is always acquired on return. */ |
114 | #define __lll_cond_lock(futex, private) \ |
115 | ((void) \ |
116 | ({ \ |
117 | int *__futex = (futex); \ |
118 | if (__glibc_unlikely (atomic_exchange_acq (__futex, 2) != 0)) \ |
119 | __lll_lock_wait (__futex, private); \ |
120 | })) |
121 | #define lll_cond_lock(futex, private) __lll_cond_lock (&(futex), private) |
122 | |
123 | |
124 | extern int __lll_clocklock_wait (int *futex, clockid_t, |
125 | const struct timespec *, |
126 | int private) attribute_hidden; |
127 | |
128 | |
129 | /* As __lll_lock, but with an absolute timeout measured against the clock |
130 | specified in CLOCKID. If the timeout occurs then return ETIMEDOUT. If |
131 | ABSTIME is invalid, return EINVAL. */ |
132 | #define __lll_clocklock(futex, clockid, abstime, private) \ |
133 | ({ \ |
134 | int *__futex = (futex); \ |
135 | int __val = 0; \ |
136 | \ |
137 | if (__glibc_unlikely \ |
138 | (atomic_compare_and_exchange_bool_acq (__futex, 1, 0))) \ |
139 | __val = __lll_clocklock_wait (__futex, clockid, abstime, private); \ |
140 | __val; \ |
141 | }) |
142 | #define lll_clocklock(futex, clockid, abstime, private) \ |
143 | __lll_clocklock (&(futex), clockid, abstime, private) |
144 | |
145 | |
146 | /* This is an expression rather than a statement even though its value is |
147 | void, so that it can be used in a comma expression or as an expression |
148 | that's cast to void. */ |
149 | /* Unconditionally set FUTEX to 0 (not acquired), releasing the lock. If FUTEX |
150 | was >1 (acquired, possibly with waiters), then wake any waiters. The waiter |
151 | that acquires the lock will set FUTEX to >1. |
152 | Evaluate PRIVATE before releasing the lock so that we do not violate the |
153 | mutex destruction requirements. Specifically, we need to ensure that |
154 | another thread can destroy the mutex (and reuse its memory) once it |
155 | acquires the lock and when there will be no further lock acquisitions; |
156 | thus, we must not access the lock after releasing it, or those accesses |
157 | could be concurrent with mutex destruction or reuse of the memory. */ |
158 | #define __lll_unlock(futex, private) \ |
159 | ((void) \ |
160 | ({ \ |
161 | int *__futex = (futex); \ |
162 | int __private = (private); \ |
163 | int __oldval = atomic_exchange_rel (__futex, 0); \ |
164 | if (__glibc_unlikely (__oldval > 1)) \ |
165 | lll_futex_wake (__futex, 1, __private); \ |
166 | })) |
167 | #define lll_unlock(futex, private) \ |
168 | __lll_unlock (&(futex), private) |
169 | |
170 | |
171 | #define lll_islocked(futex) \ |
172 | ((futex) != LLL_LOCK_INITIALIZER) |
173 | |
174 | |
175 | /* Our internal lock implementation is identical to the binary-compatible |
176 | mutex implementation. */ |
177 | |
178 | /* Initializers for lock. */ |
179 | #define LLL_LOCK_INITIALIZER (0) |
180 | #define LLL_LOCK_INITIALIZER_LOCKED (1) |
181 | |
182 | #endif /* lowlevellock.h */ |
183 | |