1 // Lightweight locks and other synchronization mechanisms.
2 //
3 // These implementations are based on WebKit's WTF::Lock. See
4 // https://webkit.org/blog/6161/locking-in-webkit/ for a description of the
5 // design.
6 #ifndef Py_INTERNAL_LOCK_H
7 #define Py_INTERNAL_LOCK_H
8 #ifdef __cplusplus
9 extern "C" {
10 #endif
11
12 #ifndef Py_BUILD_CORE
13 # error "this header requires Py_BUILD_CORE define"
14 #endif
15
16 //_Py_UNLOCKED is defined as 0 and _Py_LOCKED as 1 in Include/cpython/lock.h
17 #define _Py_HAS_PARKED 2
18 #define _Py_ONCE_INITIALIZED 4
19
20 static inline int
PyMutex_LockFast(uint8_t * lock_bits)21 PyMutex_LockFast(uint8_t *lock_bits)
22 {
23 uint8_t expected = _Py_UNLOCKED;
24 return _Py_atomic_compare_exchange_uint8(lock_bits, &expected, _Py_LOCKED);
25 }
26
27 // Checks if the mutex is currently locked.
28 static inline int
PyMutex_IsLocked(PyMutex * m)29 PyMutex_IsLocked(PyMutex *m)
30 {
31 return (_Py_atomic_load_uint8(&m->_bits) & _Py_LOCKED) != 0;
32 }
33
34 // Re-initializes the mutex after a fork to the unlocked state.
35 static inline void
_PyMutex_at_fork_reinit(PyMutex * m)36 _PyMutex_at_fork_reinit(PyMutex *m)
37 {
38 memset(m, 0, sizeof(*m));
39 }
40
41 typedef enum _PyLockFlags {
42 // Do not detach/release the GIL when waiting on the lock.
43 _Py_LOCK_DONT_DETACH = 0,
44
45 // Detach/release the GIL while waiting on the lock.
46 _PY_LOCK_DETACH = 1,
47
48 // Handle signals if interrupted while waiting on the lock.
49 _PY_LOCK_HANDLE_SIGNALS = 2,
50 } _PyLockFlags;
51
52 // Lock a mutex with an optional timeout and additional options. See
53 // _PyLockFlags for details.
54 extern PyLockStatus
55 _PyMutex_LockTimed(PyMutex *m, PyTime_t timeout_ns, _PyLockFlags flags);
56
57 // Lock a mutex with aditional options. See _PyLockFlags for details.
58 static inline void
PyMutex_LockFlags(PyMutex * m,_PyLockFlags flags)59 PyMutex_LockFlags(PyMutex *m, _PyLockFlags flags)
60 {
61 uint8_t expected = _Py_UNLOCKED;
62 if (!_Py_atomic_compare_exchange_uint8(&m->_bits, &expected, _Py_LOCKED)) {
63 _PyMutex_LockTimed(m, -1, flags);
64 }
65 }
66
67 // Unlock a mutex, returns 0 if the mutex is not locked (used for improved
68 // error messages).
69 extern int _PyMutex_TryUnlock(PyMutex *m);
70
71
72 // PyEvent is a one-time event notification
73 typedef struct {
74 uint8_t v;
75 } PyEvent;
76
77 // Check if the event is set without blocking. Returns 1 if the event is set or
78 // 0 otherwise.
79 PyAPI_FUNC(int) _PyEvent_IsSet(PyEvent *evt);
80
81 // Set the event and notify any waiting threads.
82 // Export for '_testinternalcapi' shared extension
83 PyAPI_FUNC(void) _PyEvent_Notify(PyEvent *evt);
84
85 // Wait for the event to be set. If the event is already set, then this returns
86 // immediately.
87 PyAPI_FUNC(void) PyEvent_Wait(PyEvent *evt);
88
89 // Wait for the event to be set, or until the timeout expires. If the event is
90 // already set, then this returns immediately. Returns 1 if the event was set,
91 // and 0 if the timeout expired or thread was interrupted. If `detach` is
92 // true, then the thread will detach/release the GIL while waiting.
93 PyAPI_FUNC(int)
94 PyEvent_WaitTimed(PyEvent *evt, PyTime_t timeout_ns, int detach);
95
96 // _PyRawMutex implements a word-sized mutex that that does not depend on the
97 // parking lot API, and therefore can be used in the parking lot
98 // implementation.
99 //
100 // The mutex uses a packed representation: the least significant bit is used to
101 // indicate whether the mutex is locked or not. The remaining bits are either
102 // zero or a pointer to a `struct raw_mutex_entry` (see lock.c).
103 typedef struct {
104 uintptr_t v;
105 } _PyRawMutex;
106
107 // Slow paths for lock/unlock
108 extern void _PyRawMutex_LockSlow(_PyRawMutex *m);
109 extern void _PyRawMutex_UnlockSlow(_PyRawMutex *m);
110
111 static inline void
_PyRawMutex_Lock(_PyRawMutex * m)112 _PyRawMutex_Lock(_PyRawMutex *m)
113 {
114 uintptr_t unlocked = _Py_UNLOCKED;
115 if (_Py_atomic_compare_exchange_uintptr(&m->v, &unlocked, _Py_LOCKED)) {
116 return;
117 }
118 _PyRawMutex_LockSlow(m);
119 }
120
121 static inline void
_PyRawMutex_Unlock(_PyRawMutex * m)122 _PyRawMutex_Unlock(_PyRawMutex *m)
123 {
124 uintptr_t locked = _Py_LOCKED;
125 if (_Py_atomic_compare_exchange_uintptr(&m->v, &locked, _Py_UNLOCKED)) {
126 return;
127 }
128 _PyRawMutex_UnlockSlow(m);
129 }
130
131 // Type signature for one-time initialization functions. The function should
132 // return 0 on success and -1 on failure.
133 typedef int _Py_once_fn_t(void *arg);
134
135 // (private) slow path for one time initialization
136 PyAPI_FUNC(int)
137 _PyOnceFlag_CallOnceSlow(_PyOnceFlag *flag, _Py_once_fn_t *fn, void *arg);
138
139 // Calls `fn` once using `flag`. The `arg` is passed to the call to `fn`.
140 //
141 // Returns 0 on success and -1 on failure.
142 //
143 // If `fn` returns 0 (success), then subsequent calls immediately return 0.
144 // If `fn` returns -1 (failure), then subsequent calls will retry the call.
145 static inline int
_PyOnceFlag_CallOnce(_PyOnceFlag * flag,_Py_once_fn_t * fn,void * arg)146 _PyOnceFlag_CallOnce(_PyOnceFlag *flag, _Py_once_fn_t *fn, void *arg)
147 {
148 if (_Py_atomic_load_uint8(&flag->v) == _Py_ONCE_INITIALIZED) {
149 return 0;
150 }
151 return _PyOnceFlag_CallOnceSlow(flag, fn, arg);
152 }
153
154 // A recursive mutex. The mutex should zero-initialized.
155 typedef struct {
156 PyMutex mutex;
157 unsigned long long thread; // i.e., PyThread_get_thread_ident_ex()
158 size_t level;
159 } _PyRecursiveMutex;
160
161 PyAPI_FUNC(int) _PyRecursiveMutex_IsLockedByCurrentThread(_PyRecursiveMutex *m);
162 PyAPI_FUNC(void) _PyRecursiveMutex_Lock(_PyRecursiveMutex *m);
163 PyAPI_FUNC(void) _PyRecursiveMutex_Unlock(_PyRecursiveMutex *m);
164
165
166 // A readers-writer (RW) lock. The lock supports multiple concurrent readers or
167 // a single writer. The lock is write-preferring: if a writer is waiting while
168 // the lock is read-locked then, new readers will be blocked. This avoids
169 // starvation of writers.
170 //
171 // In C++, the equivalent synchronization primitive is std::shared_mutex
172 // with shared ("read") and exclusive ("write") locking.
173 //
174 // The two least significant bits are used to indicate if the lock is
175 // write-locked and if there are parked threads (either readers or writers)
176 // waiting to acquire the lock. The remaining bits are used to indicate the
177 // number of readers holding the lock.
178 //
179 // 0b000..00000: unlocked
180 // 0bnnn..nnn00: nnn..nnn readers holding the lock
181 // 0bnnn..nnn10: nnn..nnn readers holding the lock and a writer is waiting
182 // 0b00000..010: unlocked with awoken writer about to acquire lock
183 // 0b00000..001: write-locked
184 // 0b00000..011: write-locked and readers or other writers are waiting
185 //
186 // Note that reader_count must be zero if the lock is held by a writer, and
187 // vice versa. The lock can only be held by readers or a writer, but not both.
188 //
189 // The design is optimized for simplicity of the implementation. The lock is
190 // not fair: if fairness is desired, use an additional PyMutex to serialize
191 // writers. The lock is also not reentrant.
192 typedef struct {
193 uintptr_t bits;
194 } _PyRWMutex;
195
196 // Read lock (i.e., shared lock)
197 PyAPI_FUNC(void) _PyRWMutex_RLock(_PyRWMutex *rwmutex);
198 PyAPI_FUNC(void) _PyRWMutex_RUnlock(_PyRWMutex *rwmutex);
199
200 // Write lock (i.e., exclusive lock)
201 PyAPI_FUNC(void) _PyRWMutex_Lock(_PyRWMutex *rwmutex);
202 PyAPI_FUNC(void) _PyRWMutex_Unlock(_PyRWMutex *rwmutex);
203
204 // Similar to linux seqlock: https://en.wikipedia.org/wiki/Seqlock
205 // We use a sequence number to lock the writer, an even sequence means we're unlocked, an odd
206 // sequence means we're locked. Readers will read the sequence before attempting to read the
207 // underlying data and then read the sequence number again after reading the data. If the
208 // sequence has not changed the data is valid.
209 //
210 // Differs a little bit in that we use CAS on sequence as the lock, instead of a separate spin lock.
211 // The writer can also detect that the undelering data has not changed and abandon the write
212 // and restore the previous sequence.
213 typedef struct {
214 uint32_t sequence;
215 } _PySeqLock;
216
217 // Lock the sequence lock for the writer
218 PyAPI_FUNC(void) _PySeqLock_LockWrite(_PySeqLock *seqlock);
219
220 // Unlock the sequence lock and move to the next sequence number.
221 PyAPI_FUNC(void) _PySeqLock_UnlockWrite(_PySeqLock *seqlock);
222
223 // Abandon the current update indicating that no mutations have occurred
224 // and restore the previous sequence value.
225 PyAPI_FUNC(void) _PySeqLock_AbandonWrite(_PySeqLock *seqlock);
226
227 // Begin a read operation and return the current sequence number.
228 PyAPI_FUNC(uint32_t) _PySeqLock_BeginRead(_PySeqLock *seqlock);
229
230 // End the read operation and confirm that the sequence number has not changed.
231 // Returns 1 if the read was successful or 0 if the read should be retried.
232 PyAPI_FUNC(int) _PySeqLock_EndRead(_PySeqLock *seqlock, uint32_t previous);
233
234 // Check if the lock was held during a fork and clear the lock. Returns 1
235 // if the lock was held and any associated data should be cleared.
236 PyAPI_FUNC(int) _PySeqLock_AfterFork(_PySeqLock *seqlock);
237
238 #ifdef __cplusplus
239 }
240 #endif
241 #endif /* !Py_INTERNAL_LOCK_H */
242