Repository navigation
Expand file tree
/
Copy pathparking_lot.c
More file actions
370 lines (331 loc) · 10 KB
/
Copy pathparking_lot.c
File metadata and controls
370 lines (331 loc) · 10 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
#include "Python.h"
#include "pycore_llist.h"
#include "pycore_lock.h" // _PyRawMutex
#include "pycore_parking_lot.h"
#include "pycore_pyerrors.h" // _Py_FatalErrorFormat
#include "pycore_pystate.h" // _PyThreadState_GET
#include "pycore_semaphore.h" // _PySemaphore
#include <stdbool.h>
typedef struct {
// The mutex protects the waiter queue and the num_waiters counter.
_PyRawMutex mutex;
// Linked list of `struct wait_entry` waiters in this bucket.
struct llist_node root;
size_t num_waiters;
} Bucket;
struct wait_entry {
void *park_arg;
uintptr_t addr;
_PySemaphore sema;
struct llist_node node;
bool is_unparking;
};
// Prime number to avoid correlations with memory addresses.
// We want this to be roughly proportional to the number of CPU cores
// to minimize contention on the bucket locks, but not too big to avoid
// wasting memory. The exact choice does not matter much.
#define NUM_BUCKETS 257
#define BUCKET_INIT(b, i) [i] = { .root = LLIST_INIT(b[i].root) }
#define BUCKET_INIT_2(b, i) BUCKET_INIT(b, i), BUCKET_INIT(b, i+1)
#define BUCKET_INIT_4(b, i) BUCKET_INIT_2(b, i), BUCKET_INIT_2(b, i+2)
#define BUCKET_INIT_8(b, i) BUCKET_INIT_4(b, i), BUCKET_INIT_4(b, i+4)
#define BUCKET_INIT_16(b, i) BUCKET_INIT_8(b, i), BUCKET_INIT_8(b, i+8)
#define BUCKET_INIT_32(b, i) BUCKET_INIT_16(b, i), BUCKET_INIT_16(b, i+16)
#define BUCKET_INIT_64(b, i) BUCKET_INIT_32(b, i), BUCKET_INIT_32(b, i+32)
#define BUCKET_INIT_128(b, i) BUCKET_INIT_64(b, i), BUCKET_INIT_64(b, i+64)
#define BUCKET_INIT_256(b, i) BUCKET_INIT_128(b, i), BUCKET_INIT_128(b, i+128)
// Table of waiters (hashed by address)
static Bucket buckets[NUM_BUCKETS] = {
BUCKET_INIT_256(buckets, 0),
BUCKET_INIT(buckets, 256),
};
void
_PySemaphore_Init(_PySemaphore *sema)
{
#if defined(MS_WINDOWS)
sema->platform_sem = CreateSemaphore(
NULL, // attributes
0, // initial count
10, // maximum count
NULL // unnamed
);
if (!sema->platform_sem) {
Py_FatalError("parking_lot: CreateSemaphore failed");
}
#elif defined(_Py_USE_SEMAPHORES)
if (sem_init(&sema->platform_sem, /*pshared=*/0, /*value=*/0) < 0) {
Py_FatalError("parking_lot: sem_init failed");
}
#else
if (pthread_mutex_init(&sema->mutex, NULL) != 0) {
Py_FatalError("parking_lot: pthread_mutex_init failed");
}
if (pthread_cond_init(&sema->cond, NULL)) {
Py_FatalError("parking_lot: pthread_cond_init failed");
}
sema->counter = 0;
#endif
}
void
_PySemaphore_Destroy(_PySemaphore *sema)
{
#if defined(MS_WINDOWS)
CloseHandle(sema->platform_sem);
#elif defined(_Py_USE_SEMAPHORES)
sem_destroy(&sema->platform_sem);
#else
pthread_mutex_destroy(&sema->mutex);
pthread_cond_destroy(&sema->cond);
#endif
}
static int
_PySemaphore_PlatformWait(_PySemaphore *sema, _PyTime_t timeout)
{
int res;
#if defined(MS_WINDOWS)
DWORD wait;
DWORD millis = 0;
if (timeout < 0) {
millis = INFINITE;
}
else {
millis = (DWORD) (timeout / 1000000);
}
wait = WaitForSingleObjectEx(sema->platform_sem, millis, FALSE);
if (wait == WAIT_OBJECT_0) {
res = Py_PARK_OK;
}
else if (wait == WAIT_TIMEOUT) {
res = Py_PARK_TIMEOUT;
}
else {
res = Py_PARK_INTR;
}
#elif defined(_Py_USE_SEMAPHORES)
int err;
if (timeout >= 0) {
struct timespec ts;
_PyTime_t deadline = _PyTime_Add(_PyTime_GetSystemClock(), timeout);
_PyTime_AsTimespec(deadline, &ts);
err = sem_timedwait(&sema->platform_sem, &ts);
}
else {
err = sem_wait(&sema->platform_sem);
}
if (err == -1) {
err = errno;
if (err == EINTR) {
res = Py_PARK_INTR;
}
else if (err == ETIMEDOUT) {
res = Py_PARK_TIMEOUT;
}
else {
_Py_FatalErrorFormat(__func__,
"unexpected error from semaphore: %d",
err);
}
}
else {
res = Py_PARK_OK;
}
#else
pthread_mutex_lock(&sema->mutex);
int err = 0;
if (sema->counter == 0) {
if (timeout >= 0) {
struct timespec ts;
_PyTime_t deadline = _PyTime_Add(_PyTime_GetSystemClock(), timeout);
_PyTime_AsTimespec(deadline, &ts);
err = pthread_cond_timedwait(&sema->cond, &sema->mutex, &ts);
}
else {
err = pthread_cond_wait(&sema->cond, &sema->mutex);
}
}
if (sema->counter > 0) {
sema->counter--;
res = Py_PARK_OK;
}
else if (err) {
res = Py_PARK_TIMEOUT;
}
else {
res = Py_PARK_INTR;
}
pthread_mutex_unlock(&sema->mutex);
#endif
return res;
}
int
_PySemaphore_Wait(_PySemaphore *sema, _PyTime_t timeout, int detach)
{
PyThreadState *tstate = NULL;
if (detach) {
tstate = _PyThreadState_GET();
if (tstate) {
PyEval_ReleaseThread(tstate);
}
}
int res = _PySemaphore_PlatformWait(sema, timeout);
if (detach && tstate) {
PyEval_AcquireThread(tstate);
}
return res;
}
void
_PySemaphore_Wakeup(_PySemaphore *sema)
{
#if defined(MS_WINDOWS)
if (!ReleaseSemaphore(sema->platform_sem, 1, NULL)) {
Py_FatalError("parking_lot: ReleaseSemaphore failed");
}
#elif defined(_Py_USE_SEMAPHORES)
int err = sem_post(&sema->platform_sem);
if (err != 0) {
Py_FatalError("parking_lot: sem_post failed");
}
#else
pthread_mutex_lock(&sema->mutex);
sema->counter++;
pthread_cond_signal(&sema->cond);
pthread_mutex_unlock(&sema->mutex);
#endif
}
static void
enqueue(Bucket *bucket, const void *address, struct wait_entry *wait)
{
llist_insert_tail(&bucket->root, &wait->node);
++bucket->num_waiters;
}
static struct wait_entry *
dequeue(Bucket *bucket, const void *address)
{
// find the first waiter that is waiting on `address`
struct llist_node *root = &bucket->root;
struct llist_node *node;
llist_for_each(node, root) {
struct wait_entry *wait = llist_data(node, struct wait_entry, node);
if (wait->addr == (uintptr_t)address) {
llist_remove(node);
--bucket->num_waiters;
return wait;
}
}
return NULL;
}
static void
dequeue_all(Bucket *bucket, const void *address, struct llist_node *dst)
{
// remove and append all matching waiters to dst
struct llist_node *root = &bucket->root;
struct llist_node *node;
llist_for_each_safe(node, root) {
struct wait_entry *wait = llist_data(node, struct wait_entry, node);
if (wait->addr == (uintptr_t)address) {
llist_remove(node);
llist_insert_tail(dst, node);
--bucket->num_waiters;
}
}
}
// Checks that `*addr == *expected` (only works for 1, 2, 4, or 8 bytes)
static int
atomic_memcmp(const void *addr, const void *expected, size_t addr_size)
{
switch (addr_size) {
case 1: return _Py_atomic_load_uint8(addr) == *(const uint8_t *)expected;
case 2: return _Py_atomic_load_uint16(addr) == *(const uint16_t *)expected;
case 4: return _Py_atomic_load_uint32(addr) == *(const uint32_t *)expected;
case 8: return _Py_atomic_load_uint64(addr) == *(const uint64_t *)expected;
default: Py_UNREACHABLE();
}
}
int
_PyParkingLot_Park(const void *addr, const void *expected, size_t size,
_PyTime_t timeout_ns, void *park_arg, int detach)
{
struct wait_entry wait = {
.park_arg = park_arg,
.addr = (uintptr_t)addr,
.is_unparking = false,
};
Bucket *bucket = &buckets[((uintptr_t)addr) % NUM_BUCKETS];
_PyRawMutex_Lock(&bucket->mutex);
if (!atomic_memcmp(addr, expected, size)) {
_PyRawMutex_Unlock(&bucket->mutex);
return Py_PARK_AGAIN;
}
_PySemaphore_Init(&wait.sema);
enqueue(bucket, addr, &wait);
_PyRawMutex_Unlock(&bucket->mutex);
int res = _PySemaphore_Wait(&wait.sema, timeout_ns, detach);
if (res == Py_PARK_OK) {
goto done;
}
// timeout or interrupt
_PyRawMutex_Lock(&bucket->mutex);
if (wait.is_unparking) {
_PyRawMutex_Unlock(&bucket->mutex);
// Another thread has started to unpark us. Wait until we process the
// wakeup signal.
do {
res = _PySemaphore_Wait(&wait.sema, -1, detach);
} while (res != Py_PARK_OK);
goto done;
}
else {
llist_remove(&wait.node);
--bucket->num_waiters;
}
_PyRawMutex_Unlock(&bucket->mutex);
done:
_PySemaphore_Destroy(&wait.sema);
return res;
}
void
_PyParkingLot_Unpark(const void *addr, _Py_unpark_fn_t *fn, void *arg)
{
Bucket *bucket = &buckets[((uintptr_t)addr) % NUM_BUCKETS];
// Find the first waiter that is waiting on `addr`
_PyRawMutex_Lock(&bucket->mutex);
struct wait_entry *waiter = dequeue(bucket, addr);
if (waiter) {
waiter->is_unparking = true;
int has_more_waiters = (bucket->num_waiters > 0);
fn(arg, waiter->park_arg, has_more_waiters);
}
else {
fn(arg, NULL, 0);
}
_PyRawMutex_Unlock(&bucket->mutex);
if (waiter) {
// Wakeup the waiter outside of the bucket lock
_PySemaphore_Wakeup(&waiter->sema);
}
}
void
_PyParkingLot_UnparkAll(const void *addr)
{
struct llist_node head = LLIST_INIT(head);
Bucket *bucket = &buckets[((uintptr_t)addr) % NUM_BUCKETS];
_PyRawMutex_Lock(&bucket->mutex);
dequeue_all(bucket, addr, &head);
_PyRawMutex_Unlock(&bucket->mutex);
struct llist_node *node;
llist_for_each_safe(node, &head) {
struct wait_entry *waiter = llist_data(node, struct wait_entry, node);
llist_remove(node);
_PySemaphore_Wakeup(&waiter->sema);
}
}
void
_PyParkingLot_AfterFork(void)
{
// After a fork only one thread remains. That thread cannot be blocked
// so all entries in the parking lot are for dead threads.
memset(buckets, 0, sizeof(buckets));
for (Py_ssize_t i = 0; i < NUM_BUCKETS; i++) {
llist_init(&buckets[i].root);
}
}