thread: add generic futex-based muteces
[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 #ifndef LIBVLC_DONT_WANT_MUTEX
205 static void vlc_mutex_init_common(vlc_mutex_t *mtx, bool recursive)
206 {
207     atomic_init(&mtx->value, 0);
208     atomic_init(&mtx->recursion, recursive);
209     atomic_init(&mtx->owner, NULL);
210 }
211
212 void vlc_mutex_init(vlc_mutex_t *mtx)
213 {
214     vlc_mutex_init_common(mtx, false);
215 }
216
217 void vlc_mutex_init_recursive(vlc_mutex_t *mtx)
218 {
219     vlc_mutex_init_common(mtx, true);
220 }
221
222 void vlc_mutex_destroy(vlc_mutex_t *mtx)
223 {
224     assert(atomic_load_explicit(&mtx->value, memory_order_relaxed) == 0);
225     assert(atomic_load_explicit(&mtx->recursion, memory_order_relaxed) <= 1);
226     assert(atomic_load_explicit(&mtx->owner, memory_order_relaxed) == NULL);
227     (void) mtx;
228 }
229
230 static _Thread_local char thread_self[1];
231 #define THREAD_SELF ((const void *)thread_self)
232
233 static bool vlc_mutex_held(const vlc_mutex_t *mtx)
234 {
235     /* This comparison is thread-safe:
236      * Even though other threads may modify the owner field at any time,
237      * they will never make ti compare equal to the calling thread.
238      */
239     return THREAD_SELF == atomic_load_explicit(&mtx->owner,
240                                                memory_order_relaxed);
241 }
242
243 void vlc_mutex_lock(vlc_mutex_t *mtx)
244 {
245     unsigned value;
246
247     /* This is the Drepper (non-recursive) mutex algorithm
248      * from his "Futexes are tricky" paper. The mutex can value be:
249      * - 0: the mutex is free
250      * - 1: the mutex is locked and uncontended
251      * - 2: the mutex is contended (i.e., unlock needs to wake up a waiter)
252      */
253     if (vlc_mutex_trylock(mtx) == 0)
254         return;
255
256     int canc = vlc_savecancel(); /* locking is never a cancellation point */
257
258     while ((value = atomic_exchange_explicit(&mtx->value, 2,
259                                              memory_order_acquire)) != 0)
260         vlc_atomic_wait(&mtx->value, 2);
261
262     vlc_restorecancel(canc);
263     atomic_store_explicit(&mtx->owner, THREAD_SELF, memory_order_relaxed);
264     vlc_mutex_mark(mtx);
265 }
266
267 int vlc_mutex_trylock(vlc_mutex_t *mtx)
268 {
269     /* Check the recursion counter:
270      * - 0: mutex is not recursive.
271      * - 1: mutex is recursive but free or locked non-recursively.
272      * - n > 1: mutex is recursive and locked n time(s).
273      */
274     unsigned recursion = atomic_load_explicit(&mtx->recursion,
275                                               memory_order_relaxed);
276     if (unlikely(recursion) && vlc_mutex_held(mtx)) {
277         /* This thread already owns the mutex, locks recursively.
278          * Other threads shall not have modified the recursion or owner fields.
279          */
280         atomic_store_explicit(&mtx->recursion, recursion + 1,
281                               memory_order_relaxed);
282         vlc_mutex_mark(mtx);
283         return 0;
284     } else
285         assert(!vlc_mutex_held(mtx));
286
287     unsigned value = 0;
288
289     if (atomic_compare_exchange_strong_explicit(&mtx->value, &value, 1,
290                                                 memory_order_acquire,
291                                                 memory_order_relaxed)) {
292         atomic_store_explicit(&mtx->owner, THREAD_SELF, memory_order_relaxed);
293         vlc_mutex_mark(mtx);
294         return 0;
295     }
296
297     return EBUSY;
298 }
299
300 void vlc_mutex_unlock(vlc_mutex_t *mtx)
301 {
302     assert(vlc_mutex_held(mtx));
303
304     unsigned recursion = atomic_load_explicit(&mtx->recursion,
305                                               memory_order_relaxed);
306     if (unlikely(recursion > 1)) {
307         /* Non-last recursive unlocking. */
308         atomic_store_explicit(&mtx->recursion, recursion - 1,
309                               memory_order_relaxed);
310         vlc_mutex_unmark(mtx);
311         return;
312     }
313
314     atomic_store_explicit(&mtx->owner, NULL, memory_order_relaxed);
315     vlc_mutex_unmark(mtx);
316
317     switch (atomic_exchange_explicit(&mtx->value, 0, memory_order_release)) {
318         case 2:
319             vlc_atomic_notify_one(&mtx->value);
320         case 1:
321             break;
322         default:
323             vlc_assert_unreachable();
324     }
325 }
326 #endif
327
328 void vlc_cond_init(vlc_cond_t *cond)
329 {
330     cond->head = NULL;
331     vlc_mutex_init(&cond->lock);
332 }
333
334 void vlc_cond_init_daytime(vlc_cond_t *cond)
335 {
336     vlc_cond_init(cond);
337 }
338
339 void vlc_cond_destroy(vlc_cond_t *cond)
340 {
341     assert(cond->head == NULL);
342     vlc_mutex_destroy(&cond->lock);
343 }
344
345 struct vlc_cond_waiter {
346     struct vlc_cond_waiter **pprev, *next;
347     atomic_uint value;
348     vlc_cond_t *cond;
349     vlc_mutex_t *mutex;
350 };
351
352 static void vlc_cond_signal_waiter(struct vlc_cond_waiter *waiter)
353 {
354     waiter->pprev = &waiter->next;
355     waiter->next = NULL;
356     atomic_fetch_add_explicit(&waiter->value, 1, memory_order_relaxed);
357     vlc_atomic_notify_one(&waiter->value);
358 }
359
360 void vlc_cond_signal(vlc_cond_t *cond)
361 {
362     struct vlc_cond_waiter *waiter;
363
364     /* Some call sites signal their condition variable without holding the
365      * corresponding lock. Thus an extra lock is needed here to ensure the
366      * consistency of the linked list and the lifetime of its elements.
367      * If all call sites locked cleanly, the inner lock would be unnecessary.
368      */
369     vlc_mutex_lock(&cond->lock);
370     waiter = cond->head;
371
372     if (waiter != NULL) {
373         struct vlc_cond_waiter *next = waiter->next;
374         struct vlc_cond_waiter **pprev = waiter->pprev;
375
376         *pprev = next;
377
378         if (next != NULL)
379             next->pprev = pprev;
380
381         vlc_cond_signal_waiter(waiter);
382     }
383
384     vlc_mutex_unlock(&cond->lock);
385 }
386
387 void vlc_cond_broadcast(vlc_cond_t *cond)
388 {
389     struct vlc_cond_waiter *waiter;
390
391     vlc_mutex_lock(&cond->lock);
392     waiter = cond->head;
393     cond->head = NULL;
394
395     /* Keep the lock here so that waiters don't go out of scope */
396     while (waiter != NULL) {
397         struct vlc_cond_waiter *next = waiter->next;
398
399         vlc_cond_signal_waiter(waiter);
400         waiter = next;
401     }
402
403     vlc_mutex_unlock(&cond->lock);
404 }
405
406 static void vlc_cond_wait_prepare(struct vlc_cond_waiter *waiter,
407                                   vlc_cond_t *cond, vlc_mutex_t *mutex)
408 {
409     struct vlc_cond_waiter *next;
410
411     waiter->pprev = &cond->head;
412     atomic_init(&waiter->value, 0);
413     waiter->cond = cond;
414     waiter->mutex = mutex;
415
416     vlc_mutex_lock(&cond->lock);
417     next = cond->head;
418     cond->head = waiter;
419     waiter->next = next;
420
421     if (next != NULL)
422         next->pprev = &waiter->next;
423
424     vlc_mutex_unlock(&cond->lock);
425     vlc_cancel_addr_prepare(&waiter->value);
426     vlc_mutex_unlock(mutex);
427 }
428
429 static void vlc_cond_wait_finish(struct vlc_cond_waiter *waiter,
430                                  vlc_cond_t *cond, vlc_mutex_t *mutex)
431 {
432     struct vlc_cond_waiter *next;
433
434     /* If this waiter is still on the linked list, remove it before it goes
435      * out of scope. Otherwise, this is a no-op.
436      */
437     vlc_mutex_lock(&cond->lock);
438     next = waiter->next;
439     *(waiter->pprev) = next;
440
441     if (next != NULL)
442         next->pprev = waiter->pprev;
443
444     vlc_mutex_unlock(&cond->lock);
445
446     /* Lock the caller's mutex as required by condition variable semantics. */
447     vlc_mutex_lock(mutex);
448     vlc_cancel_addr_finish(&waiter->value);
449 }
450
451 static void vlc_cond_wait_cleanup(void *data)
452 {
453     struct vlc_cond_waiter *waiter = data;
454
455     vlc_cond_wait_finish(waiter, waiter->cond, waiter->mutex);
456 }
457
458 void vlc_cond_wait(vlc_cond_t *cond, vlc_mutex_t *mutex)
459 {
460     struct vlc_cond_waiter waiter;
461
462     vlc_cond_wait_prepare(&waiter, cond, mutex);
463     vlc_cleanup_push(vlc_cond_wait_cleanup, &waiter);
464     vlc_atomic_wait(&waiter.value, 0);
465     vlc_cleanup_pop();
466     vlc_cond_wait_cleanup(&waiter);
467 }
468
469 int vlc_cond_timedwait(vlc_cond_t *cond, vlc_mutex_t *mutex,
470                        vlc_tick_t deadline)
471 {
472     struct vlc_cond_waiter waiter;
473     int ret;
474
475     vlc_cond_wait_prepare(&waiter, cond, mutex);
476     vlc_cleanup_push(vlc_cond_wait_cleanup, &waiter);
477     ret = vlc_atomic_timedwait(&waiter.value, 0, deadline);
478     vlc_cleanup_pop();
479     vlc_cond_wait_cleanup(&waiter);
480
481     return ret;
482 }
483
484 int vlc_cond_timedwait_daytime(vlc_cond_t *cond, vlc_mutex_t *mutex,
485                                time_t deadline)
486 {
487     struct vlc_cond_waiter waiter;
488     int ret;
489
490     vlc_cond_wait_prepare(&waiter, cond, mutex);
491     vlc_cleanup_push(vlc_cond_wait_cleanup, &waiter);
492     ret = vlc_atomic_timedwait_daytime(&waiter.value, 0, deadline);
493     vlc_cleanup_pop();
494     vlc_cond_wait_cleanup(&waiter);
495
496     return ret;
497 }
498
499 #ifdef LIBVLC_NEED_RWLOCK
500 /*** Generic read/write locks ***/
501 #include <stdlib.h>
502 #include <limits.h>
503 /* NOTE:
504  * lock->state is a signed long integer:
505  *  - The sign bit is set when the lock is held for writing.
506  *  - The other bits code the number of times the lock is held for reading.
507  * Consequently:
508  *  - The value is negative if and only if the lock is held for writing.
509  *  - The value is zero if and only if the lock is not held at all.
510  */
511 #define READER_MASK LONG_MAX
512 #define WRITER_BIT  LONG_MIN
513
514 void vlc_rwlock_init (vlc_rwlock_t *lock)
515 {
516     vlc_mutex_init (&lock->mutex);
517     vlc_cond_init (&lock->wait);
518     lock->state = 0;
519 }
520
521 void vlc_rwlock_destroy (vlc_rwlock_t *lock)
522 {
523     vlc_cond_destroy (&lock->wait);
524     vlc_mutex_destroy (&lock->mutex);
525 }
526
527 void vlc_rwlock_rdlock (vlc_rwlock_t *lock)
528 {
529     vlc_mutex_lock (&lock->mutex);
530     /* Recursive read-locking is allowed.
531      * Ensure that there is no active writer. */
532     while (lock->state < 0)
533     {
534         assert (lock->state == WRITER_BIT);
535         mutex_cleanup_push (&lock->mutex);
536         vlc_cond_wait (&lock->wait, &lock->mutex);
537         vlc_cleanup_pop ();
538     }
539     if (unlikely(lock->state >= READER_MASK))
540         abort (); /* An overflow is certainly a recursion bug. */
541     lock->state++;
542     vlc_mutex_unlock (&lock->mutex);
543 }
544
545 void vlc_rwlock_wrlock (vlc_rwlock_t *lock)
546 {
547     vlc_mutex_lock (&lock->mutex);
548     /* Wait until nobody owns the lock in any way. */
549     while (lock->state != 0)
550     {
551         mutex_cleanup_push (&lock->mutex);
552         vlc_cond_wait (&lock->wait, &lock->mutex);
553         vlc_cleanup_pop ();
554     }
555     lock->state = WRITER_BIT;
556     vlc_mutex_unlock (&lock->mutex);
557 }
558
559 void vlc_rwlock_unlock (vlc_rwlock_t *lock)
560 {
561     vlc_mutex_lock (&lock->mutex);
562     if (lock->state < 0)
563     {   /* Write unlock */
564         assert (lock->state == WRITER_BIT);
565         /* Let reader and writer compete. OS scheduler decides who wins. */
566         lock->state = 0;
567         vlc_cond_broadcast (&lock->wait);
568     }
569     else
570     {   /* Read unlock */
571         assert (lock->state > 0);
572         /* If there are no readers left, wake up one pending writer. */
573         if (--lock->state == 0)
574             vlc_cond_signal (&lock->wait);
575     }
576     vlc_mutex_unlock (&lock->mutex);
577 }
578 #endif /* LIBVLC_NEED_RWLOCK */
579
580 /*** Generic semaphores ***/
581
582 void vlc_sem_init (vlc_sem_t *sem, unsigned value)
583 {
584     atomic_init(&sem->value, value);
585 }
586
587 int vlc_sem_post (vlc_sem_t *sem)
588 {
589     unsigned exp = atomic_load_explicit(&sem->value, memory_order_relaxed);
590
591     do
592     {
593         if (unlikely(exp == UINT_MAX))
594            return EOVERFLOW;
595     } while (!atomic_compare_exchange_weak_explicit(&sem->value, &exp, exp + 1,
596                                                     memory_order_release,
597                                                     memory_order_relaxed));
598
599     vlc_atomic_notify_one(&sem->value);
600     return 0;
601 }
602
603 void vlc_sem_wait (vlc_sem_t *sem)
604 {
605     unsigned exp = 1;
606
607     while (!atomic_compare_exchange_weak_explicit(&sem->value, &exp, exp - 1,
608                                                   memory_order_acquire,
609                                                   memory_order_relaxed))
610     {
611         if (likely(exp == 0))
612         {
613             vlc_atomic_wait(&sem->value, 0);
614             exp = 1;
615         }
616     }
617 }
618
619 int vlc_sem_timedwait(vlc_sem_t *sem, vlc_tick_t deadline)
620 {
621     unsigned exp = 1;
622
623     while (!atomic_compare_exchange_weak_explicit(&sem->value, &exp, exp - 1,
624                                                   memory_order_acquire,
625                                                   memory_order_relaxed))
626     {
627         if (likely(exp == 0))
628         {
629             int ret = vlc_atomic_timedwait(&sem->value, 0, deadline);
630             if (ret)
631                 return ret;
632
633             exp = 1;
634         }
635     }
636
637     return 0;
638 }