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
77extern void __lll_lock_wait_private (int *futex) attribute_hidden;
78extern 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
124extern 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