1/* Copyright (C) 2002-2021 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3 Contributed by Ulrich Drepper <drepper@redhat.com>, 2002.
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 <https://www.gnu.org/licenses/>. */
18
19#include <assert.h>
20#include <errno.h>
21#include <stdlib.h>
22#include <unistd.h>
23#include <sys/param.h>
24#include <not-cancel.h>
25#include "pthreadP.h"
26#include <atomic.h>
27#include <futex-internal.h>
28#include <stap-probe.h>
29
30#ifndef lll_lock_elision
31#define lll_lock_elision(lock, try_lock, private) ({ \
32 lll_lock (lock, private); 0; })
33#endif
34
35#ifndef lll_trylock_elision
36#define lll_trylock_elision(a,t) lll_trylock(a)
37#endif
38
39/* Some of the following definitions differ when pthread_mutex_cond_lock.c
40 includes this file. */
41#ifndef LLL_MUTEX_LOCK
42# define LLL_MUTEX_LOCK(mutex) \
43 lll_lock ((mutex)->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex))
44# define LLL_MUTEX_TRYLOCK(mutex) \
45 lll_trylock ((mutex)->__data.__lock)
46# define LLL_ROBUST_MUTEX_LOCK_MODIFIER 0
47# define LLL_MUTEX_LOCK_ELISION(mutex) \
48 lll_lock_elision ((mutex)->__data.__lock, (mutex)->__data.__elision, \
49 PTHREAD_MUTEX_PSHARED (mutex))
50# define LLL_MUTEX_TRYLOCK_ELISION(mutex) \
51 lll_trylock_elision((mutex)->__data.__lock, (mutex)->__data.__elision, \
52 PTHREAD_MUTEX_PSHARED (mutex))
53#endif
54
55#ifndef FORCE_ELISION
56#define FORCE_ELISION(m, s)
57#endif
58
59static int __pthread_mutex_lock_full (pthread_mutex_t *mutex)
60 __attribute_noinline__;
61
62int
63__pthread_mutex_lock (pthread_mutex_t *mutex)
64{
65 /* See concurrency notes regarding mutex type which is loaded from __kind
66 in struct __pthread_mutex_s in sysdeps/nptl/bits/thread-shared-types.h. */
67 unsigned int type = PTHREAD_MUTEX_TYPE_ELISION (mutex);
68
69 LIBC_PROBE (mutex_entry, 1, mutex);
70
71 if (__builtin_expect (type & ~(PTHREAD_MUTEX_KIND_MASK_NP
72 | PTHREAD_MUTEX_ELISION_FLAGS_NP), 0))
73 return __pthread_mutex_lock_full (mutex);
74
75 if (__glibc_likely (type == PTHREAD_MUTEX_TIMED_NP))
76 {
77 FORCE_ELISION (mutex, goto elision);
78 simple:
79 /* Normal mutex. */
80 LLL_MUTEX_LOCK (mutex);
81 assert (mutex->__data.__owner == 0);
82 }
83#ifdef HAVE_ELISION
84 else if (__glibc_likely (type == PTHREAD_MUTEX_TIMED_ELISION_NP))
85 {
86 elision: __attribute__((unused))
87 /* This case can never happen on a system without elision,
88 as the mutex type initialization functions will not
89 allow to set the elision flags. */
90 /* Don't record owner or users for elision case. This is a
91 tail call. */
92 return LLL_MUTEX_LOCK_ELISION (mutex);
93 }
94#endif
95 else if (__builtin_expect (PTHREAD_MUTEX_TYPE (mutex)
96 == PTHREAD_MUTEX_RECURSIVE_NP, 1))
97 {
98 /* Recursive mutex. */
99 pid_t id = THREAD_GETMEM (THREAD_SELF, tid);
100
101 /* Check whether we already hold the mutex. */
102 if (mutex->__data.__owner == id)
103 {
104 /* Just bump the counter. */
105 if (__glibc_unlikely (mutex->__data.__count + 1 == 0))
106 /* Overflow of the counter. */
107 return EAGAIN;
108
109 ++mutex->__data.__count;
110
111 return 0;
112 }
113
114 /* We have to get the mutex. */
115 LLL_MUTEX_LOCK (mutex);
116
117 assert (mutex->__data.__owner == 0);
118 mutex->__data.__count = 1;
119 }
120 else if (__builtin_expect (PTHREAD_MUTEX_TYPE (mutex)
121 == PTHREAD_MUTEX_ADAPTIVE_NP, 1))
122 {
123 if (LLL_MUTEX_TRYLOCK (mutex) != 0)
124 {
125 int cnt = 0;
126 int max_cnt = MIN (max_adaptive_count (),
127 mutex->__data.__spins * 2 + 10);
128 do
129 {
130 if (cnt++ >= max_cnt)
131 {
132 LLL_MUTEX_LOCK (mutex);
133 break;
134 }
135 atomic_spin_nop ();
136 }
137 while (LLL_MUTEX_TRYLOCK (mutex) != 0);
138
139 mutex->__data.__spins += (cnt - mutex->__data.__spins) / 8;
140 }
141 assert (mutex->__data.__owner == 0);
142 }
143 else
144 {
145 pid_t id = THREAD_GETMEM (THREAD_SELF, tid);
146 assert (PTHREAD_MUTEX_TYPE (mutex) == PTHREAD_MUTEX_ERRORCHECK_NP);
147 /* Check whether we already hold the mutex. */
148 if (__glibc_unlikely (mutex->__data.__owner == id))
149 return EDEADLK;
150 goto simple;
151 }
152
153 pid_t id = THREAD_GETMEM (THREAD_SELF, tid);
154
155 /* Record the ownership. */
156 mutex->__data.__owner = id;
157#ifndef NO_INCR
158 ++mutex->__data.__nusers;
159#endif
160
161 LIBC_PROBE (mutex_acquired, 1, mutex);
162
163 return 0;
164}
165
166static int
167__pthread_mutex_lock_full (pthread_mutex_t *mutex)
168{
169 int oldval;
170 pid_t id = THREAD_GETMEM (THREAD_SELF, tid);
171
172 switch (PTHREAD_MUTEX_TYPE (mutex))
173 {
174 case PTHREAD_MUTEX_ROBUST_RECURSIVE_NP:
175 case PTHREAD_MUTEX_ROBUST_ERRORCHECK_NP:
176 case PTHREAD_MUTEX_ROBUST_NORMAL_NP:
177 case PTHREAD_MUTEX_ROBUST_ADAPTIVE_NP:
178 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending,
179 &mutex->__data.__list.__next);
180 /* We need to set op_pending before starting the operation. Also
181 see comments at ENQUEUE_MUTEX. */
182 __asm ("" ::: "memory");
183
184 oldval = mutex->__data.__lock;
185 /* This is set to FUTEX_WAITERS iff we might have shared the
186 FUTEX_WAITERS flag with other threads, and therefore need to keep it
187 set to avoid lost wake-ups. We have the same requirement in the
188 simple mutex algorithm.
189 We start with value zero for a normal mutex, and FUTEX_WAITERS if we
190 are building the special case mutexes for use from within condition
191 variables. */
192 unsigned int assume_other_futex_waiters = LLL_ROBUST_MUTEX_LOCK_MODIFIER;
193 while (1)
194 {
195 /* Try to acquire the lock through a CAS from 0 (not acquired) to
196 our TID | assume_other_futex_waiters. */
197 if (__glibc_likely (oldval == 0))
198 {
199 oldval
200 = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock,
201 id | assume_other_futex_waiters, 0);
202 if (__glibc_likely (oldval == 0))
203 break;
204 }
205
206 if ((oldval & FUTEX_OWNER_DIED) != 0)
207 {
208 /* The previous owner died. Try locking the mutex. */
209 int newval = id;
210#ifdef NO_INCR
211 /* We are not taking assume_other_futex_waiters into accoount
212 here simply because we'll set FUTEX_WAITERS anyway. */
213 newval |= FUTEX_WAITERS;
214#else
215 newval |= (oldval & FUTEX_WAITERS) | assume_other_futex_waiters;
216#endif
217
218 newval
219 = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock,
220 newval, oldval);
221
222 if (newval != oldval)
223 {
224 oldval = newval;
225 continue;
226 }
227
228 /* We got the mutex. */
229 mutex->__data.__count = 1;
230 /* But it is inconsistent unless marked otherwise. */
231 mutex->__data.__owner = PTHREAD_MUTEX_INCONSISTENT;
232
233 /* We must not enqueue the mutex before we have acquired it.
234 Also see comments at ENQUEUE_MUTEX. */
235 __asm ("" ::: "memory");
236 ENQUEUE_MUTEX (mutex);
237 /* We need to clear op_pending after we enqueue the mutex. */
238 __asm ("" ::: "memory");
239 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
240
241 /* Note that we deliberately exit here. If we fall
242 through to the end of the function __nusers would be
243 incremented which is not correct because the old
244 owner has to be discounted. If we are not supposed
245 to increment __nusers we actually have to decrement
246 it here. */
247#ifdef NO_INCR
248 --mutex->__data.__nusers;
249#endif
250
251 return EOWNERDEAD;
252 }
253
254 /* Check whether we already hold the mutex. */
255 if (__glibc_unlikely ((oldval & FUTEX_TID_MASK) == id))
256 {
257 int kind = PTHREAD_MUTEX_TYPE (mutex);
258 if (kind == PTHREAD_MUTEX_ROBUST_ERRORCHECK_NP)
259 {
260 /* We do not need to ensure ordering wrt another memory
261 access. Also see comments at ENQUEUE_MUTEX. */
262 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending,
263 NULL);
264 return EDEADLK;
265 }
266
267 if (kind == PTHREAD_MUTEX_ROBUST_RECURSIVE_NP)
268 {
269 /* We do not need to ensure ordering wrt another memory
270 access. */
271 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending,
272 NULL);
273
274 /* Just bump the counter. */
275 if (__glibc_unlikely (mutex->__data.__count + 1 == 0))
276 /* Overflow of the counter. */
277 return EAGAIN;
278
279 ++mutex->__data.__count;
280
281 return 0;
282 }
283 }
284
285 /* We cannot acquire the mutex nor has its owner died. Thus, try
286 to block using futexes. Set FUTEX_WAITERS if necessary so that
287 other threads are aware that there are potentially threads
288 blocked on the futex. Restart if oldval changed in the
289 meantime. */
290 if ((oldval & FUTEX_WAITERS) == 0)
291 {
292 if (atomic_compare_and_exchange_bool_acq (&mutex->__data.__lock,
293 oldval | FUTEX_WAITERS,
294 oldval)
295 != 0)
296 {
297 oldval = mutex->__data.__lock;
298 continue;
299 }
300 oldval |= FUTEX_WAITERS;
301 }
302
303 /* It is now possible that we share the FUTEX_WAITERS flag with
304 another thread; therefore, update assume_other_futex_waiters so
305 that we do not forget about this when handling other cases
306 above and thus do not cause lost wake-ups. */
307 assume_other_futex_waiters |= FUTEX_WAITERS;
308
309 /* Block using the futex and reload current lock value. */
310 futex_wait ((unsigned int *) &mutex->__data.__lock, oldval,
311 PTHREAD_ROBUST_MUTEX_PSHARED (mutex));
312 oldval = mutex->__data.__lock;
313 }
314
315 /* We have acquired the mutex; check if it is still consistent. */
316 if (__builtin_expect (mutex->__data.__owner
317 == PTHREAD_MUTEX_NOTRECOVERABLE, 0))
318 {
319 /* This mutex is now not recoverable. */
320 mutex->__data.__count = 0;
321 int private = PTHREAD_ROBUST_MUTEX_PSHARED (mutex);
322 lll_unlock (mutex->__data.__lock, private);
323 /* FIXME This violates the mutex destruction requirements. See
324 __pthread_mutex_unlock_full. */
325 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
326 return ENOTRECOVERABLE;
327 }
328
329 mutex->__data.__count = 1;
330 /* We must not enqueue the mutex before we have acquired it.
331 Also see comments at ENQUEUE_MUTEX. */
332 __asm ("" ::: "memory");
333 ENQUEUE_MUTEX (mutex);
334 /* We need to clear op_pending after we enqueue the mutex. */
335 __asm ("" ::: "memory");
336 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
337 break;
338
339 /* The PI support requires the Linux futex system call. If that's not
340 available, pthread_mutex_init should never have allowed the type to
341 be set. So it will get the default case for an invalid type. */
342#ifdef __NR_futex
343 case PTHREAD_MUTEX_PI_RECURSIVE_NP:
344 case PTHREAD_MUTEX_PI_ERRORCHECK_NP:
345 case PTHREAD_MUTEX_PI_NORMAL_NP:
346 case PTHREAD_MUTEX_PI_ADAPTIVE_NP:
347 case PTHREAD_MUTEX_PI_ROBUST_RECURSIVE_NP:
348 case PTHREAD_MUTEX_PI_ROBUST_ERRORCHECK_NP:
349 case PTHREAD_MUTEX_PI_ROBUST_NORMAL_NP:
350 case PTHREAD_MUTEX_PI_ROBUST_ADAPTIVE_NP:
351 {
352 int kind, robust;
353 {
354 /* See concurrency notes regarding __kind in struct __pthread_mutex_s
355 in sysdeps/nptl/bits/thread-shared-types.h. */
356 int mutex_kind = atomic_load_relaxed (&(mutex->__data.__kind));
357 kind = mutex_kind & PTHREAD_MUTEX_KIND_MASK_NP;
358 robust = mutex_kind & PTHREAD_MUTEX_ROBUST_NORMAL_NP;
359 }
360
361 if (robust)
362 {
363 /* Note: robust PI futexes are signaled by setting bit 0. */
364 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending,
365 (void *) (((uintptr_t) &mutex->__data.__list.__next)
366 | 1));
367 /* We need to set op_pending before starting the operation. Also
368 see comments at ENQUEUE_MUTEX. */
369 __asm ("" ::: "memory");
370 }
371
372 oldval = mutex->__data.__lock;
373
374 /* Check whether we already hold the mutex. */
375 if (__glibc_unlikely ((oldval & FUTEX_TID_MASK) == id))
376 {
377 if (kind == PTHREAD_MUTEX_ERRORCHECK_NP)
378 {
379 /* We do not need to ensure ordering wrt another memory
380 access. */
381 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
382 return EDEADLK;
383 }
384
385 if (kind == PTHREAD_MUTEX_RECURSIVE_NP)
386 {
387 /* We do not need to ensure ordering wrt another memory
388 access. */
389 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
390
391 /* Just bump the counter. */
392 if (__glibc_unlikely (mutex->__data.__count + 1 == 0))
393 /* Overflow of the counter. */
394 return EAGAIN;
395
396 ++mutex->__data.__count;
397
398 return 0;
399 }
400 }
401
402 int newval = id;
403# ifdef NO_INCR
404 newval |= FUTEX_WAITERS;
405# endif
406 oldval = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock,
407 newval, 0);
408
409 if (oldval != 0)
410 {
411 /* The mutex is locked. The kernel will now take care of
412 everything. */
413 int private = (robust
414 ? PTHREAD_ROBUST_MUTEX_PSHARED (mutex)
415 : PTHREAD_MUTEX_PSHARED (mutex));
416 int e = futex_lock_pi64 (&mutex->__data.__lock, NULL, private);
417 if (e == ESRCH || e == EDEADLK)
418 {
419 assert (e != EDEADLK
420 || (kind != PTHREAD_MUTEX_ERRORCHECK_NP
421 && kind != PTHREAD_MUTEX_RECURSIVE_NP));
422 /* ESRCH can happen only for non-robust PI mutexes where
423 the owner of the lock died. */
424 assert (e != ESRCH || !robust);
425
426 /* Delay the thread indefinitely. */
427 while (1)
428 __futex_abstimed_wait64 (&(unsigned int){0}, 0,
429 0 /* ignored */, NULL, private);
430 }
431
432 oldval = mutex->__data.__lock;
433
434 assert (robust || (oldval & FUTEX_OWNER_DIED) == 0);
435 }
436
437 if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED))
438 {
439 atomic_and (&mutex->__data.__lock, ~FUTEX_OWNER_DIED);
440
441 /* We got the mutex. */
442 mutex->__data.__count = 1;
443 /* But it is inconsistent unless marked otherwise. */
444 mutex->__data.__owner = PTHREAD_MUTEX_INCONSISTENT;
445
446 /* We must not enqueue the mutex before we have acquired it.
447 Also see comments at ENQUEUE_MUTEX. */
448 __asm ("" ::: "memory");
449 ENQUEUE_MUTEX_PI (mutex);
450 /* We need to clear op_pending after we enqueue the mutex. */
451 __asm ("" ::: "memory");
452 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
453
454 /* Note that we deliberately exit here. If we fall
455 through to the end of the function __nusers would be
456 incremented which is not correct because the old owner
457 has to be discounted. If we are not supposed to
458 increment __nusers we actually have to decrement it here. */
459# ifdef NO_INCR
460 --mutex->__data.__nusers;
461# endif
462
463 return EOWNERDEAD;
464 }
465
466 if (robust
467 && __builtin_expect (mutex->__data.__owner
468 == PTHREAD_MUTEX_NOTRECOVERABLE, 0))
469 {
470 /* This mutex is now not recoverable. */
471 mutex->__data.__count = 0;
472
473 futex_unlock_pi ((unsigned int *) &mutex->__data.__lock,
474 PTHREAD_ROBUST_MUTEX_PSHARED (mutex));
475
476 /* To the kernel, this will be visible after the kernel has
477 acquired the mutex in the syscall. */
478 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
479 return ENOTRECOVERABLE;
480 }
481
482 mutex->__data.__count = 1;
483 if (robust)
484 {
485 /* We must not enqueue the mutex before we have acquired it.
486 Also see comments at ENQUEUE_MUTEX. */
487 __asm ("" ::: "memory");
488 ENQUEUE_MUTEX_PI (mutex);
489 /* We need to clear op_pending after we enqueue the mutex. */
490 __asm ("" ::: "memory");
491 THREAD_SETMEM (THREAD_SELF, robust_head.list_op_pending, NULL);
492 }
493 }
494 break;
495#endif /* __NR_futex. */
496
497 case PTHREAD_MUTEX_PP_RECURSIVE_NP:
498 case PTHREAD_MUTEX_PP_ERRORCHECK_NP:
499 case PTHREAD_MUTEX_PP_NORMAL_NP:
500 case PTHREAD_MUTEX_PP_ADAPTIVE_NP:
501 {
502 /* See concurrency notes regarding __kind in struct __pthread_mutex_s
503 in sysdeps/nptl/bits/thread-shared-types.h. */
504 int kind = atomic_load_relaxed (&(mutex->__data.__kind))
505 & PTHREAD_MUTEX_KIND_MASK_NP;
506
507 oldval = mutex->__data.__lock;
508
509 /* Check whether we already hold the mutex. */
510 if (mutex->__data.__owner == id)
511 {
512 if (kind == PTHREAD_MUTEX_ERRORCHECK_NP)
513 return EDEADLK;
514
515 if (kind == PTHREAD_MUTEX_RECURSIVE_NP)
516 {
517 /* Just bump the counter. */
518 if (__glibc_unlikely (mutex->__data.__count + 1 == 0))
519 /* Overflow of the counter. */
520 return EAGAIN;
521
522 ++mutex->__data.__count;
523
524 return 0;
525 }
526 }
527
528 int oldprio = -1, ceilval;
529 do
530 {
531 int ceiling = (oldval & PTHREAD_MUTEX_PRIO_CEILING_MASK)
532 >> PTHREAD_MUTEX_PRIO_CEILING_SHIFT;
533
534 if (__pthread_current_priority () > ceiling)
535 {
536 if (oldprio != -1)
537 __pthread_tpp_change_priority (oldprio, -1);
538 return EINVAL;
539 }
540
541 int retval = __pthread_tpp_change_priority (oldprio, ceiling);
542 if (retval)
543 return retval;
544
545 ceilval = ceiling << PTHREAD_MUTEX_PRIO_CEILING_SHIFT;
546 oldprio = ceiling;
547
548 oldval
549 = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock,
550#ifdef NO_INCR
551 ceilval | 2,
552#else
553 ceilval | 1,
554#endif
555 ceilval);
556
557 if (oldval == ceilval)
558 break;
559
560 do
561 {
562 oldval
563 = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock,
564 ceilval | 2,
565 ceilval | 1);
566
567 if ((oldval & PTHREAD_MUTEX_PRIO_CEILING_MASK) != ceilval)
568 break;
569
570 if (oldval != ceilval)
571 futex_wait ((unsigned int * ) &mutex->__data.__lock,
572 ceilval | 2,
573 PTHREAD_MUTEX_PSHARED (mutex));
574 }
575 while (atomic_compare_and_exchange_val_acq (&mutex->__data.__lock,
576 ceilval | 2, ceilval)
577 != ceilval);
578 }
579 while ((oldval & PTHREAD_MUTEX_PRIO_CEILING_MASK) != ceilval);
580
581 assert (mutex->__data.__owner == 0);
582 mutex->__data.__count = 1;
583 }
584 break;
585
586 default:
587 /* Correct code cannot set any other type. */
588 return EINVAL;
589 }
590
591 /* Record the ownership. */
592 mutex->__data.__owner = id;
593#ifndef NO_INCR
594 ++mutex->__data.__nusers;
595#endif
596
597 LIBC_PROBE (mutex_acquired, 1, mutex);
598
599 return 0;
600}
601#ifndef __pthread_mutex_lock
602weak_alias (__pthread_mutex_lock, pthread_mutex_lock)
603hidden_def (__pthread_mutex_lock)
604#endif
605
606
607#ifdef NO_INCR
608void
609__pthread_mutex_cond_lock_adjust (pthread_mutex_t *mutex)
610{
611 /* See concurrency notes regarding __kind in struct __pthread_mutex_s
612 in sysdeps/nptl/bits/thread-shared-types.h. */
613 int mutex_kind = atomic_load_relaxed (&(mutex->__data.__kind));
614 assert ((mutex_kind & PTHREAD_MUTEX_PRIO_INHERIT_NP) != 0);
615 assert ((mutex_kind & PTHREAD_MUTEX_ROBUST_NORMAL_NP) == 0);
616 assert ((mutex_kind & PTHREAD_MUTEX_PSHARED_BIT) == 0);
617
618 /* Record the ownership. */
619 pid_t id = THREAD_GETMEM (THREAD_SELF, tid);
620 mutex->__data.__owner = id;
621
622 if (mutex_kind == PTHREAD_MUTEX_PI_RECURSIVE_NP)
623 ++mutex->__data.__count;
624}
625#endif
626