bdb3c9d687f5cf291a2f6188568a71d6c3a3513f
[vlc.git] / src / misc / threads.c
1 /*****************************************************************************
2  * threads.c: LibVLC generic thread support
3  *****************************************************************************
4  * Copyright (C) 2009-2016 RĂ©mi Denis-Courmont
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation; either version 2.1 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
19  *****************************************************************************/
20
21 #ifdef HAVE_CONFIG_H
22 # include "config.h"
23 #endif
24
25 #include <assert.h>
26 #include <errno.h>
27 #include <limits.h>
28 #include <stdatomic.h>
29
30 #include <vlc_common.h>
31 #include "libvlc.h"
32
33 /* <stdatomic.h> types cannot be used in the C++ view of <vlc_threads.h> */
34 struct vlc_suuint { union { unsigned int value; }; };
35
36 static_assert (sizeof (atomic_uint) <= sizeof (struct vlc_suuint),
37                "Size mismatch");
38 static_assert (alignof (atomic_uint) <= alignof (struct vlc_suuint),
39                "Alignment mismatch");
40
41 /*** Global locks ***/
42
43 void vlc_global_mutex (unsigned n, bool acquire)
44 {
45     static vlc_mutex_t locks[] = {
46         VLC_STATIC_MUTEX,
47         VLC_STATIC_MUTEX,
48         VLC_STATIC_MUTEX,
49         VLC_STATIC_MUTEX,
50 #ifdef _WIN32
51         VLC_STATIC_MUTEX, // For MTA holder
52 #endif
53     };
54     static_assert (VLC_MAX_MUTEX == (sizeof (locks) / sizeof (locks[0])),
55                    "Wrong number of global mutexes");
56     assert (n < (sizeof (locks) / sizeof (locks[0])));
57
58     vlc_mutex_t *lock = locks + n;
59     if (acquire)
60         vlc_mutex_lock (lock);
61     else
62         vlc_mutex_unlock (lock);
63 }
64
65 #ifndef NDEBUG
66 # ifdef HAVE_SEARCH_H
67 #  include <search.h>
68 # endif
69
70 struct vlc_lock_mark
71 {
72     const void *object;
73     uintptr_t refs;
74 };
75
76 static int vlc_lock_mark_cmp(const void *a, const void *b)
77 {
78     const struct vlc_lock_mark *ma = a, *mb = b;
79
80     if (ma->object == mb->object)
81         return 0;
82
83     return ((uintptr_t)(ma->object) > (uintptr_t)(mb->object)) ? +1 : -1;
84 }
85
86 static void vlc_lock_mark(const void *lock, void **rootp)
87 {
88     struct vlc_lock_mark *mark = malloc(sizeof (*mark));
89     if (unlikely(mark == NULL))
90         abort();
91
92     mark->object = lock;
93     mark->refs = 0;
94
95     void **entry = tsearch(mark, rootp, vlc_lock_mark_cmp);
96     if (unlikely(entry == NULL))
97         abort();
98
99     if (unlikely(*entry != mark)) {
100         /* Recursive locking: lock is already in the tree */
101         free(mark);
102         mark = *entry;
103     }
104
105     mark->refs++;
106 }
107
108 static void vlc_lock_unmark(const void *lock, void **rootp)
109 {
110     struct vlc_lock_mark *mark = &(struct vlc_lock_mark){ lock, 0 };
111     void **entry = tfind(mark, rootp, vlc_lock_mark_cmp);
112
113     assert(entry != NULL);
114     mark = *entry;
115     assert(mark->refs > 0);
116
117     if (likely(--mark->refs == 0)) {
118         tdelete(mark, rootp, vlc_lock_mark_cmp);
119         free(mark);
120     }
121 }
122
123 static bool vlc_lock_marked(const void *lock, void **rootp)
124 {
125     struct vlc_lock_mark *mark = &(struct vlc_lock_mark){ lock, 0 };
126
127     return tfind(mark, rootp, vlc_lock_mark_cmp) != NULL;
128 }
129
130 static _Thread_local void *vlc_mutex_marks = NULL;
131
132 void vlc_mutex_mark(const vlc_mutex_t *mutex)
133 {
134     vlc_lock_mark(mutex, &vlc_mutex_marks);
135 }
136
137 void vlc_mutex_unmark(const vlc_mutex_t *mutex)
138 {
139     vlc_lock_unmark(mutex, &vlc_mutex_marks);
140 }
141
142 bool vlc_mutex_marked(const vlc_mutex_t *mutex)
143 {
144     return vlc_lock_marked(mutex, &vlc_mutex_marks);
145 }
146 #else
147 bool vlc_mutex_marked(const vlc_mutex_t *mutex)
148 {
149     return true;
150 }
151 #endif
152
153 #if defined (_WIN32) && (_WIN32_WINNT < _WIN32_WINNT_WIN8)
154 /* Cannot define OS version-dependent stuff in public headers */
155 # undef LIBVLC_NEED_SLEEP
156 #endif
157
158 #if defined(_WIN32) || defined(__ANDROID__)
159 static void do_vlc_cancel_addr_clear(void *addr)
160 {
161     vlc_cancel_addr_clear(addr);
162 }
163
164 static void vlc_cancel_addr_prepare(atomic_uint *addr)
165 {
166     /* Let thread subsystem on address to broadcast for cancellation */
167     vlc_cancel_addr_set(addr);
168     vlc_cleanup_push(do_vlc_cancel_addr_clear, addr);
169     /* Check if cancellation was pending before vlc_cancel_addr_set() */
170     vlc_testcancel();
171     vlc_cleanup_pop();
172 }
173
174 static void vlc_cancel_addr_finish(atomic_uint *addr)
175 {
176     vlc_cancel_addr_clear(addr);
177     /* Act on cancellation as potential wake-up source */
178     vlc_testcancel();
179 }
180 #else
181 # define vlc_cancel_addr_prepare(addr) ((void)0)
182 # define vlc_cancel_addr_finish(addr) ((void)0)
183 #endif
184
185 #ifdef LIBVLC_NEED_SLEEP
186 void (vlc_tick_wait)(vlc_tick_t deadline)
187 {
188     atomic_uint value = ATOMIC_VAR_INIT(0);
189
190     vlc_cancel_addr_prepare(&value);
191
192     while (vlc_atomic_timedwait(&value, 0, deadline) == 0)
193         vlc_testcancel();
194
195     vlc_cancel_addr_finish(&value);
196 }
197
198 void (vlc_tick_sleep)(vlc_tick_t delay)
199 {
200     vlc_tick_wait(vlc_tick_now() + delay);
201 }
202 #endif
203
204 void vlc_cond_init(vlc_cond_t *cond)
205 {
206     cond->head = NULL;
207     vlc_mutex_init(&cond->lock);
208 }
209
210 void vlc_cond_init_daytime(vlc_cond_t *cond)
211 {
212     vlc_cond_init(cond);
213 }
214
215 void vlc_cond_destroy(vlc_cond_t *cond)
216 {
217     assert(cond->head == NULL);
218     vlc_mutex_destroy(&cond->lock);
219 }
220
221 struct vlc_cond_waiter {
222     struct vlc_cond_waiter **pprev, *next;
223     atomic_uint value;
224     vlc_cond_t *cond;
225     vlc_mutex_t *mutex;
226 };
227
228 static void vlc_cond_signal_waiter(struct vlc_cond_waiter *waiter)
229 {
230     waiter->pprev = &waiter->next;
231     waiter->next = NULL;
232     atomic_fetch_add_explicit(&waiter->value, 1, memory_order_relaxed);
233     vlc_atomic_notify_one(&waiter->value);
234 }
235
236 void vlc_cond_signal(vlc_cond_t *cond)
237 {
238     struct vlc_cond_waiter *waiter;
239
240     /* Some call sites signal their condition variable without holding the
241      * corresponding lock. Thus an extra lock is needed here to ensure the
242      * consistency of the linked list and the lifetime of its elements.
243      * If all call sites locked cleanly, the inner lock would be unnecessary.
244      */
245     vlc_mutex_lock(&cond->lock);
246     waiter = cond->head;
247
248     if (waiter != NULL) {
249         struct vlc_cond_waiter *next = waiter->next;
250         struct vlc_cond_waiter **pprev = waiter->pprev;
251
252         *pprev = next;
253
254         if (next != NULL)
255             next->pprev = pprev;
256
257         vlc_cond_signal_waiter(waiter);
258     }
259
260     vlc_mutex_unlock(&cond->lock);
261 }
262
263 void vlc_cond_broadcast(vlc_cond_t *cond)
264 {
265     struct vlc_cond_waiter *waiter;
266
267     vlc_mutex_lock(&cond->lock);
268     waiter = cond->head;
269     cond->head = NULL;
270
271     /* Keep the lock here so that waiters don't go out of scope */
272     while (waiter != NULL) {
273         struct vlc_cond_waiter *next = waiter->next;
274
275         vlc_cond_signal_waiter(waiter);
276         waiter = next;
277     }
278
279     vlc_mutex_unlock(&cond->lock);
280 }
281
282 static void vlc_cond_wait_prepare(struct vlc_cond_waiter *waiter,
283                                   vlc_cond_t *cond, vlc_mutex_t *mutex)
284 {
285     struct vlc_cond_waiter *next;
286
287     waiter->pprev = &cond->head;
288     atomic_init(&waiter->value, 0);
289     waiter->cond = cond;
290     waiter->mutex = mutex;
291
292     vlc_mutex_lock(&cond->lock);
293     next = cond->head;
294     cond->head = waiter;
295     waiter->next = next;
296
297     if (next != NULL)
298         next->pprev = &waiter->next;
299
300     vlc_mutex_unlock(&cond->lock);
301     vlc_cancel_addr_prepare(&waiter->value);
302     vlc_mutex_unlock(mutex);
303 }
304
305 static void vlc_cond_wait_finish(struct vlc_cond_waiter *waiter,
306                                  vlc_cond_t *cond, vlc_mutex_t *mutex)
307 {
308     struct vlc_cond_waiter *next;
309
310     /* If this waiter is still on the linked list, remove it before it goes
311      * out of scope. Otherwise, this is a no-op.
312      */
313     vlc_mutex_lock(&cond->lock);
314     next = waiter->next;
315     *(waiter->pprev) = next;
316
317     if (next != NULL)
318         next->pprev = waiter->pprev;
319
320     vlc_mutex_unlock(&cond->lock);
321
322     /* Lock the caller's mutex as required by condition variable semantics. */
323     vlc_mutex_lock(mutex);
324     vlc_cancel_addr_finish(&waiter->value);
325 }
326
327 static void vlc_cond_wait_cleanup(void *data)
328 {
329     struct vlc_cond_waiter *waiter = data;
330
331     vlc_cond_wait_finish(waiter, waiter->cond, waiter->mutex);
332 }
333
334 void vlc_cond_wait(vlc_cond_t *cond, vlc_mutex_t *mutex)
335 {
336     struct vlc_cond_waiter waiter;
337
338     vlc_cond_wait_prepare(&waiter, cond, mutex);
339     vlc_cleanup_push(vlc_cond_wait_cleanup, &waiter);
340     vlc_atomic_wait(&waiter.value, 0);
341     vlc_cleanup_pop();
342     vlc_cond_wait_cleanup(&waiter);
343 }
344
345 int vlc_cond_timedwait(vlc_cond_t *cond, vlc_mutex_t *mutex,
346                        vlc_tick_t deadline)
347 {
348     struct vlc_cond_waiter waiter;
349     int ret;
350
351     vlc_cond_wait_prepare(&waiter, cond, mutex);
352     vlc_cleanup_push(vlc_cond_wait_cleanup, &waiter);
353     ret = vlc_atomic_timedwait(&waiter.value, 0, deadline);
354     vlc_cleanup_pop();
355     vlc_cond_wait_cleanup(&waiter);
356
357     return ret;
358 }
359
360 int vlc_cond_timedwait_daytime(vlc_cond_t *cond, vlc_mutex_t *mutex,
361                                time_t deadline)
362 {
363     struct vlc_cond_waiter waiter;
364     int ret;
365
366     vlc_cond_wait_prepare(&waiter, cond, mutex);
367     vlc_cleanup_push(vlc_cond_wait_cleanup, &waiter);
368     ret = vlc_atomic_timedwait_daytime(&waiter.value, 0, deadline);
369     vlc_cleanup_pop();
370     vlc_cond_wait_cleanup(&waiter);
371
372     return ret;
373 }
374
375 #ifdef LIBVLC_NEED_RWLOCK
376 /*** Generic read/write locks ***/
377 #include <stdlib.h>
378 #include <limits.h>
379 /* NOTE:
380  * lock->state is a signed long integer:
381  *  - The sign bit is set when the lock is held for writing.
382  *  - The other bits code the number of times the lock is held for reading.
383  * Consequently:
384  *  - The value is negative if and only if the lock is held for writing.
385  *  - The value is zero if and only if the lock is not held at all.
386  */
387 #define READER_MASK LONG_MAX
388 #define WRITER_BIT  LONG_MIN
389
390 void vlc_rwlock_init (vlc_rwlock_t *lock)
391 {
392     vlc_mutex_init (&lock->mutex);
393     vlc_cond_init (&lock->wait);
394     lock->state = 0;
395 }
396
397 void vlc_rwlock_destroy (vlc_rwlock_t *lock)
398 {
399     vlc_cond_destroy (&lock->wait);
400     vlc_mutex_destroy (&lock->mutex);
401 }
402
403 void vlc_rwlock_rdlock (vlc_rwlock_t *lock)
404 {
405     vlc_mutex_lock (&lock->mutex);
406     /* Recursive read-locking is allowed.
407      * Ensure that there is no active writer. */
408     while (lock->state < 0)
409     {
410         assert (lock->state == WRITER_BIT);
411         mutex_cleanup_push (&lock->mutex);
412         vlc_cond_wait (&lock->wait, &lock->mutex);
413         vlc_cleanup_pop ();
414     }
415     if (unlikely(lock->state >= READER_MASK))
416         abort (); /* An overflow is certainly a recursion bug. */
417     lock->state++;
418     vlc_mutex_unlock (&lock->mutex);
419 }
420
421 void vlc_rwlock_wrlock (vlc_rwlock_t *lock)
422 {
423     vlc_mutex_lock (&lock->mutex);
424     /* Wait until nobody owns the lock in any way. */
425     while (lock->state != 0)
426     {
427         mutex_cleanup_push (&lock->mutex);
428         vlc_cond_wait (&lock->wait, &lock->mutex);
429         vlc_cleanup_pop ();
430     }
431     lock->state = WRITER_BIT;
432     vlc_mutex_unlock (&lock->mutex);
433 }
434
435 void vlc_rwlock_unlock (vlc_rwlock_t *lock)
436 {
437     vlc_mutex_lock (&lock->mutex);
438     if (lock->state < 0)
439     {   /* Write unlock */
440         assert (lock->state == WRITER_BIT);
441         /* Let reader and writer compete. OS scheduler decides who wins. */
442         lock->state = 0;
443         vlc_cond_broadcast (&lock->wait);
444     }
445     else
446     {   /* Read unlock */
447         assert (lock->state > 0);
448         /* If there are no readers left, wake up one pending writer. */
449         if (--lock->state == 0)
450             vlc_cond_signal (&lock->wait);
451     }
452     vlc_mutex_unlock (&lock->mutex);
453 }
454 #endif /* LIBVLC_NEED_RWLOCK */
455
456 /*** Generic semaphores ***/
457
458 void vlc_sem_init (vlc_sem_t *sem, unsigned value)
459 {
460     atomic_init(&sem->value, value);
461 }
462
463 int vlc_sem_post (vlc_sem_t *sem)
464 {
465     unsigned exp = atomic_load_explicit(&sem->value, memory_order_relaxed);
466
467     do
468     {
469         if (unlikely(exp == UINT_MAX))
470            return EOVERFLOW;
471     } while (!atomic_compare_exchange_weak_explicit(&sem->value, &exp, exp + 1,
472                                                     memory_order_release,
473                                                     memory_order_relaxed));
474
475     vlc_atomic_notify_one(&sem->value);
476     return 0;
477 }
478
479 void vlc_sem_wait (vlc_sem_t *sem)
480 {
481     unsigned exp = 1;
482
483     while (!atomic_compare_exchange_weak_explicit(&sem->value, &exp, exp - 1,
484                                                   memory_order_acquire,
485                                                   memory_order_relaxed))
486     {
487         if (likely(exp == 0))
488         {
489             vlc_atomic_wait(&sem->value, 0);
490             exp = 1;
491         }
492     }
493 }
494
495 int vlc_sem_timedwait(vlc_sem_t *sem, vlc_tick_t deadline)
496 {
497     unsigned exp = 1;
498
499     while (!atomic_compare_exchange_weak_explicit(&sem->value, &exp, exp - 1,
500                                                   memory_order_acquire,
501                                                   memory_order_relaxed))
502     {
503         if (likely(exp == 0))
504         {
505             int ret = vlc_atomic_timedwait(&sem->value, 0, deadline);
506             if (ret)
507                 return ret;
508
509             exp = 1;
510         }
511     }
512
513     return 0;
514 }