blob: 4fec7535c720c31d106478fd5cb2431c5befc6c0 [file] [log] [blame]
The Android Open Source Project1dc9e472009-03-03 19:28:35 -08001/*
2 * Copyright (C) 2008 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in
12 * the documentation and/or other materials provided with the
13 * distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
Pierre Peifferd0c884d2012-02-22 16:40:15 +010028
Elliott Hughes6f94de32013-02-12 06:06:22 +000029#include <pthread.h>
Elliott Hughes3e898472013-02-12 16:40:24 +000030
31#include <errno.h>
32#include <limits.h>
Yabin Cui86fc96f2015-01-29 21:50:48 -080033#include <stdatomic.h>
Yabin Cui17393b02015-03-21 15:08:25 -070034#include <string.h>
Yabin Cui86fc96f2015-01-29 21:50:48 -080035#include <sys/cdefs.h>
Elliott Hughes84114c82013-07-17 13:33:19 -070036#include <sys/mman.h>
Pierre Peifferd0c884d2012-02-22 16:40:15 +010037#include <unistd.h>
38
Pierre Peifferd0c884d2012-02-22 16:40:15 +010039#include "pthread_internal.h"
Elliott Hugheseb847bc2013-10-09 15:50:50 -070040
Elliott Hughes04303f52014-09-18 16:11:59 -070041#include "private/bionic_constants.h"
Elliott Hugheseb847bc2013-10-09 15:50:50 -070042#include "private/bionic_futex.h"
Yabin Cui86fc96f2015-01-29 21:50:48 -080043#include "private/bionic_systrace.h"
Elliott Hughes04303f52014-09-18 16:11:59 -070044#include "private/bionic_time_conversions.h"
Elliott Hugheseb847bc2013-10-09 15:50:50 -070045#include "private/bionic_tls.h"
The Android Open Source Project1dc9e472009-03-03 19:28:35 -080046
Yabin Cuie69c2452015-02-13 16:21:25 -080047/* a mutex attribute holds the following fields
48 *
49 * bits: name description
50 * 0-3 type type of mutex
51 * 4 shared process-shared flag
52 */
53#define MUTEXATTR_TYPE_MASK 0x000f
54#define MUTEXATTR_SHARED_MASK 0x0010
55
56int pthread_mutexattr_init(pthread_mutexattr_t *attr)
57{
58 *attr = PTHREAD_MUTEX_DEFAULT;
59 return 0;
60}
61
62int pthread_mutexattr_destroy(pthread_mutexattr_t *attr)
63{
64 *attr = -1;
65 return 0;
66}
67
68int pthread_mutexattr_gettype(const pthread_mutexattr_t *attr, int *type_p)
69{
70 int type = (*attr & MUTEXATTR_TYPE_MASK);
71
72 if (type < PTHREAD_MUTEX_NORMAL || type > PTHREAD_MUTEX_ERRORCHECK) {
73 return EINVAL;
74 }
75
76 *type_p = type;
77 return 0;
78}
79
80int pthread_mutexattr_settype(pthread_mutexattr_t *attr, int type)
81{
82 if (type < PTHREAD_MUTEX_NORMAL || type > PTHREAD_MUTEX_ERRORCHECK ) {
83 return EINVAL;
84 }
85
86 *attr = (*attr & ~MUTEXATTR_TYPE_MASK) | type;
87 return 0;
88}
89
90/* process-shared mutexes are not supported at the moment */
91
92int pthread_mutexattr_setpshared(pthread_mutexattr_t *attr, int pshared)
93{
94 switch (pshared) {
95 case PTHREAD_PROCESS_PRIVATE:
96 *attr &= ~MUTEXATTR_SHARED_MASK;
97 return 0;
98
99 case PTHREAD_PROCESS_SHARED:
100 /* our current implementation of pthread actually supports shared
101 * mutexes but won't cleanup if a process dies with the mutex held.
102 * Nevertheless, it's better than nothing. Shared mutexes are used
103 * by surfaceflinger and audioflinger.
104 */
105 *attr |= MUTEXATTR_SHARED_MASK;
106 return 0;
107 }
108 return EINVAL;
109}
110
111int pthread_mutexattr_getpshared(const pthread_mutexattr_t* attr, int* pshared) {
112 *pshared = (*attr & MUTEXATTR_SHARED_MASK) ? PTHREAD_PROCESS_SHARED : PTHREAD_PROCESS_PRIVATE;
113 return 0;
114}
115
116/* a mutex contains a state value and a owner_tid.
117 * The value is implemented as a 16-bit integer holding the following fields:
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800118 *
119 * bits: name description
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800120 * 15-14 type mutex type
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700121 * 13 shared process-shared flag
122 * 12-2 counter counter of recursive mutexes
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800123 * 1-0 state lock state (0, 1 or 2)
Yabin Cuie69c2452015-02-13 16:21:25 -0800124 *
125 * The owner_tid is used only in recursive and errorcheck mutex to hold the mutex owner thread tid.
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800126 */
127
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100128/* Convenience macro, creates a mask of 'bits' bits that starts from
129 * the 'shift'-th least significant bit in a 32-bit word.
130 *
131 * Examples: FIELD_MASK(0,4) -> 0xf
132 * FIELD_MASK(16,9) -> 0x1ff0000
133 */
134#define FIELD_MASK(shift,bits) (((1 << (bits))-1) << (shift))
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800135
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100136/* This one is used to create a bit pattern from a given field value */
137#define FIELD_TO_BITS(val,shift,bits) (((val) & ((1 << (bits))-1)) << (shift))
David 'Digit' Turner022d3032011-12-07 14:02:17 +0100138
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100139/* And this one does the opposite, i.e. extract a field's value from a bit pattern */
140#define FIELD_FROM_BITS(val,shift,bits) (((val) >> (shift)) & ((1 << (bits))-1))
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800141
Yabin Cuie69c2452015-02-13 16:21:25 -0800142
143/* Convenience macros.
144 *
145 * These are used to form or modify the bit pattern of a given mutex value
146 */
147
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100148/* Mutex state:
149 *
150 * 0 for unlocked
151 * 1 for locked, no waiters
152 * 2 for locked, maybe waiters
153 */
154#define MUTEX_STATE_SHIFT 0
155#define MUTEX_STATE_LEN 2
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800156
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100157#define MUTEX_STATE_MASK FIELD_MASK(MUTEX_STATE_SHIFT, MUTEX_STATE_LEN)
158#define MUTEX_STATE_FROM_BITS(v) FIELD_FROM_BITS(v, MUTEX_STATE_SHIFT, MUTEX_STATE_LEN)
159#define MUTEX_STATE_TO_BITS(v) FIELD_TO_BITS(v, MUTEX_STATE_SHIFT, MUTEX_STATE_LEN)
160
Yabin Cui17393b02015-03-21 15:08:25 -0700161#define MUTEX_STATE_UNLOCKED 0 /* must be 0 to match PTHREAD_MUTEX_INITIALIZER */
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100162#define MUTEX_STATE_LOCKED_UNCONTENDED 1 /* must be 1 due to atomic dec in unlock operation */
163#define MUTEX_STATE_LOCKED_CONTENDED 2 /* must be 1 + LOCKED_UNCONTENDED due to atomic dec */
164
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100165#define MUTEX_STATE_BITS_UNLOCKED MUTEX_STATE_TO_BITS(MUTEX_STATE_UNLOCKED)
166#define MUTEX_STATE_BITS_LOCKED_UNCONTENDED MUTEX_STATE_TO_BITS(MUTEX_STATE_LOCKED_UNCONTENDED)
167#define MUTEX_STATE_BITS_LOCKED_CONTENDED MUTEX_STATE_TO_BITS(MUTEX_STATE_LOCKED_CONTENDED)
168
169/* return true iff the mutex if locked with no waiters */
170#define MUTEX_STATE_BITS_IS_LOCKED_UNCONTENDED(v) (((v) & MUTEX_STATE_MASK) == MUTEX_STATE_BITS_LOCKED_UNCONTENDED)
171
172/* return true iff the mutex if locked with maybe waiters */
173#define MUTEX_STATE_BITS_IS_LOCKED_CONTENDED(v) (((v) & MUTEX_STATE_MASK) == MUTEX_STATE_BITS_LOCKED_CONTENDED)
174
175/* used to flip from LOCKED_UNCONTENDED to LOCKED_CONTENDED */
176#define MUTEX_STATE_BITS_FLIP_CONTENTION(v) ((v) ^ (MUTEX_STATE_BITS_LOCKED_CONTENDED ^ MUTEX_STATE_BITS_LOCKED_UNCONTENDED))
177
178/* Mutex counter:
179 *
180 * We need to check for overflow before incrementing, and we also need to
181 * detect when the counter is 0
182 */
183#define MUTEX_COUNTER_SHIFT 2
184#define MUTEX_COUNTER_LEN 11
185#define MUTEX_COUNTER_MASK FIELD_MASK(MUTEX_COUNTER_SHIFT, MUTEX_COUNTER_LEN)
186
187#define MUTEX_COUNTER_BITS_WILL_OVERFLOW(v) (((v) & MUTEX_COUNTER_MASK) == MUTEX_COUNTER_MASK)
188#define MUTEX_COUNTER_BITS_IS_ZERO(v) (((v) & MUTEX_COUNTER_MASK) == 0)
189
190/* Used to increment the counter directly after overflow has been checked */
Yabin Cui86fc96f2015-01-29 21:50:48 -0800191#define MUTEX_COUNTER_BITS_ONE FIELD_TO_BITS(1, MUTEX_COUNTER_SHIFT,MUTEX_COUNTER_LEN)
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100192
193/* Mutex shared bit flag
194 *
195 * This flag is set to indicate that the mutex is shared among processes.
196 * This changes the futex opcode we use for futex wait/wake operations
197 * (non-shared operations are much faster).
198 */
199#define MUTEX_SHARED_SHIFT 13
200#define MUTEX_SHARED_MASK FIELD_MASK(MUTEX_SHARED_SHIFT,1)
201
202/* Mutex type:
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100203 * We support normal, recursive and errorcheck mutexes.
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100204 */
205#define MUTEX_TYPE_SHIFT 14
206#define MUTEX_TYPE_LEN 2
207#define MUTEX_TYPE_MASK FIELD_MASK(MUTEX_TYPE_SHIFT,MUTEX_TYPE_LEN)
208
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100209#define MUTEX_TYPE_TO_BITS(t) FIELD_TO_BITS(t, MUTEX_TYPE_SHIFT, MUTEX_TYPE_LEN)
210
Yabin Cui17393b02015-03-21 15:08:25 -0700211#define MUTEX_TYPE_BITS_NORMAL MUTEX_TYPE_TO_BITS(PTHREAD_MUTEX_NORMAL)
212#define MUTEX_TYPE_BITS_RECURSIVE MUTEX_TYPE_TO_BITS(PTHREAD_MUTEX_RECURSIVE)
213#define MUTEX_TYPE_BITS_ERRORCHECK MUTEX_TYPE_TO_BITS(PTHREAD_MUTEX_ERRORCHECK)
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100214
Yabin Cui17393b02015-03-21 15:08:25 -0700215struct pthread_mutex_internal_t {
Yabin Cuie69c2452015-02-13 16:21:25 -0800216 _Atomic(uint16_t) state;
Yabin Cui17393b02015-03-21 15:08:25 -0700217#if defined(__LP64__)
Yabin Cuie69c2452015-02-13 16:21:25 -0800218 uint16_t __pad;
219 atomic_int owner_tid;
220 char __reserved[32];
221#else
222 _Atomic(uint16_t) owner_tid;
Yabin Cui17393b02015-03-21 15:08:25 -0700223#endif
Yabin Cuie69c2452015-02-13 16:21:25 -0800224} __attribute__((aligned(4)));
Yabin Cui86fc96f2015-01-29 21:50:48 -0800225
Yabin Cui17393b02015-03-21 15:08:25 -0700226static_assert(sizeof(pthread_mutex_t) == sizeof(pthread_mutex_internal_t),
227 "pthread_mutex_t should actually be pthread_mutex_internal_t in implementation.");
228
229// For binary compatibility with old version of pthread_mutex_t, we can't use more strict alignment
230// than 4-byte alignment.
231static_assert(alignof(pthread_mutex_t) == 4,
232 "pthread_mutex_t should fulfill the alignment of pthread_mutex_internal_t.");
233
234static inline pthread_mutex_internal_t* __get_internal_mutex(pthread_mutex_t* mutex_interface) {
235 return reinterpret_cast<pthread_mutex_internal_t*>(mutex_interface);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800236}
237
Yabin Cui17393b02015-03-21 15:08:25 -0700238int pthread_mutex_init(pthread_mutex_t* mutex_interface, const pthread_mutexattr_t* attr) {
239 pthread_mutex_internal_t* mutex = __get_internal_mutex(mutex_interface);
240
241 memset(mutex, 0, sizeof(pthread_mutex_internal_t));
Yabin Cui86fc96f2015-01-29 21:50:48 -0800242
Elliott Hughesd4e753f2013-07-16 12:45:46 -0700243 if (__predict_true(attr == NULL)) {
Yabin Cui17393b02015-03-21 15:08:25 -0700244 atomic_init(&mutex->state, MUTEX_TYPE_BITS_NORMAL);
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700245 return 0;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800246 }
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700247
Yabin Cuie69c2452015-02-13 16:21:25 -0800248 uint16_t state = 0;
Elliott Hughesdff72032013-12-11 14:54:00 -0800249 if ((*attr & MUTEXATTR_SHARED_MASK) != 0) {
Yabin Cui17393b02015-03-21 15:08:25 -0700250 state |= MUTEX_SHARED_MASK;
Elliott Hughesdff72032013-12-11 14:54:00 -0800251 }
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700252
253 switch (*attr & MUTEXATTR_TYPE_MASK) {
254 case PTHREAD_MUTEX_NORMAL:
Yabin Cuie69c2452015-02-13 16:21:25 -0800255 state |= MUTEX_TYPE_BITS_NORMAL;
256 break;
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700257 case PTHREAD_MUTEX_RECURSIVE:
Yabin Cuie69c2452015-02-13 16:21:25 -0800258 state |= MUTEX_TYPE_BITS_RECURSIVE;
259 break;
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700260 case PTHREAD_MUTEX_ERRORCHECK:
Yabin Cuie69c2452015-02-13 16:21:25 -0800261 state |= MUTEX_TYPE_BITS_ERRORCHECK;
262 break;
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700263 default:
264 return EINVAL;
265 }
266
Yabin Cui17393b02015-03-21 15:08:25 -0700267 atomic_init(&mutex->state, state);
Yabin Cuie69c2452015-02-13 16:21:25 -0800268 atomic_init(&mutex->owner_tid, 0);
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700269 return 0;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800270}
271
Yabin Cui17393b02015-03-21 15:08:25 -0700272static inline __always_inline int __pthread_normal_mutex_trylock(pthread_mutex_internal_t* mutex,
Yabin Cuie69c2452015-02-13 16:21:25 -0800273 uint16_t shared) {
274 const uint16_t unlocked = shared | MUTEX_STATE_BITS_UNLOCKED;
275 const uint16_t locked_uncontended = shared | MUTEX_STATE_BITS_LOCKED_UNCONTENDED;
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800276
Yabin Cuie69c2452015-02-13 16:21:25 -0800277 uint16_t old_state = unlocked;
Yabin Cui17393b02015-03-21 15:08:25 -0700278 if (__predict_true(atomic_compare_exchange_strong_explicit(&mutex->state, &old_state,
279 locked_uncontended, memory_order_acquire, memory_order_relaxed))) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800280 return 0;
281 }
282 return EBUSY;
283}
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800284
285/*
Yabin Cui86fc96f2015-01-29 21:50:48 -0800286 * Lock a mutex of type NORMAL.
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800287 *
288 * As noted above, there are three states:
289 * 0 (unlocked, no contention)
290 * 1 (locked, no contention)
291 * 2 (locked, contention)
292 *
293 * Non-recursive mutexes don't use the thread-id or counter fields, and the
294 * "type" value is zero, so the only bits that will be set are the ones in
295 * the lock state field.
296 */
Yabin Cui17393b02015-03-21 15:08:25 -0700297static inline __always_inline int __pthread_normal_mutex_lock(pthread_mutex_internal_t* mutex,
Yabin Cuie69c2452015-02-13 16:21:25 -0800298 uint16_t shared,
Yabin Cui17393b02015-03-21 15:08:25 -0700299 const timespec* abs_timeout_or_null,
300 clockid_t clock) {
301 if (__predict_true(__pthread_normal_mutex_trylock(mutex, shared) == 0)) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800302 return 0;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800303 }
Yabin Cui86fc96f2015-01-29 21:50:48 -0800304
305 ScopedTrace trace("Contending for pthread mutex");
306
Yabin Cuie69c2452015-02-13 16:21:25 -0800307 const uint16_t unlocked = shared | MUTEX_STATE_BITS_UNLOCKED;
308 const uint16_t locked_contended = shared | MUTEX_STATE_BITS_LOCKED_CONTENDED;
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800309
Yabin Cui86fc96f2015-01-29 21:50:48 -0800310 // We want to go to sleep until the mutex is available, which requires
311 // promoting it to locked_contended. We need to swap in the new state
Yabin Cui17393b02015-03-21 15:08:25 -0700312 // and then wait until somebody wakes us up.
Yabin Cui86fc96f2015-01-29 21:50:48 -0800313 // An atomic_exchange is used to compete with other threads for the lock.
314 // If it returns unlocked, we have acquired the lock, otherwise another
315 // thread still holds the lock and we should wait again.
316 // If lock is acquired, an acquire fence is needed to make all memory accesses
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800317 // made by other threads visible to the current CPU.
Yabin Cui17393b02015-03-21 15:08:25 -0700318 while (atomic_exchange_explicit(&mutex->state, locked_contended,
Yabin Cui86fc96f2015-01-29 21:50:48 -0800319 memory_order_acquire) != unlocked) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800320 timespec ts;
321 timespec* rel_timeout = NULL;
322 if (abs_timeout_or_null != NULL) {
323 rel_timeout = &ts;
324 if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout_or_null, clock)) {
325 return ETIMEDOUT;
326 }
327 }
Yabin Cui17393b02015-03-21 15:08:25 -0700328 if (__futex_wait_ex(&mutex->state, shared, locked_contended, rel_timeout) == -ETIMEDOUT) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800329 return ETIMEDOUT;
330 }
Yabin Cui86fc96f2015-01-29 21:50:48 -0800331 }
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800332 return 0;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800333}
334
335/*
Yabin Cuie69c2452015-02-13 16:21:25 -0800336 * Release a normal mutex. The caller is responsible for determining
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800337 * that we are in fact the owner of this lock.
338 */
Yabin Cui17393b02015-03-21 15:08:25 -0700339static inline __always_inline void __pthread_normal_mutex_unlock(pthread_mutex_internal_t* mutex,
Yabin Cuie69c2452015-02-13 16:21:25 -0800340 uint16_t shared) {
341 const uint16_t unlocked = shared | MUTEX_STATE_BITS_UNLOCKED;
342 const uint16_t locked_contended = shared | MUTEX_STATE_BITS_LOCKED_CONTENDED;
Andy McFaddenfcd00eb2010-05-28 13:31:45 -0700343
Yabin Cui86fc96f2015-01-29 21:50:48 -0800344 // We use an atomic_exchange to release the lock. If locked_contended state
345 // is returned, some threads is waiting for the lock and we need to wake up
346 // one of them.
347 // A release fence is required to make previous stores visible to next
348 // lock owner threads.
Yabin Cui17393b02015-03-21 15:08:25 -0700349 if (atomic_exchange_explicit(&mutex->state, unlocked,
Yabin Cui86fc96f2015-01-29 21:50:48 -0800350 memory_order_release) == locked_contended) {
351 // Wake up one waiting thread. We don't know which thread will be
352 // woken or when it'll start executing -- futexes make no guarantees
353 // here. There may not even be a thread waiting.
354 //
355 // The newly-woken thread will replace the unlocked state we just set above
356 // with locked_contended state, which means that when it eventually releases
357 // the mutex it will also call FUTEX_WAKE. This results in one extra wake
358 // call whenever a lock is contended, but let us avoid forgetting anyone
359 // without requiring us to track the number of sleepers.
360 //
361 // It's possible for another thread to sneak in and grab the lock between
362 // the exchange above and the wake call below. If the new thread is "slow"
363 // and holds the lock for a while, we'll wake up a sleeper, which will swap
364 // in locked_uncontended state and then go back to sleep since the lock is
365 // still held. If the new thread is "fast", running to completion before
366 // we call wake, the thread we eventually wake will find an unlocked mutex
367 // and will execute. Either way we have correct behavior and nobody is
368 // orphaned on the wait queue.
Yabin Cui17393b02015-03-21 15:08:25 -0700369 __futex_wake_ex(&mutex->state, shared, 1);
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800370 }
371}
372
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800373/* This common inlined function is used to increment the counter of a recursive mutex.
David 'Digit' Turner022d3032011-12-07 14:02:17 +0100374 *
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800375 * If the counter overflows, it will return EAGAIN.
376 * Otherwise, it atomically increments the counter and returns 0.
David 'Digit' Turner022d3032011-12-07 14:02:17 +0100377 *
David 'Digit' Turner022d3032011-12-07 14:02:17 +0100378 */
Yabin Cui17393b02015-03-21 15:08:25 -0700379static inline __always_inline int __recursive_increment(pthread_mutex_internal_t* mutex,
Yabin Cuie69c2452015-02-13 16:21:25 -0800380 uint16_t old_state) {
Yabin Cui86fc96f2015-01-29 21:50:48 -0800381 // Detect recursive lock overflow and return EAGAIN.
382 // This is safe because only the owner thread can modify the
383 // counter bits in the mutex value.
Yabin Cui17393b02015-03-21 15:08:25 -0700384 if (MUTEX_COUNTER_BITS_WILL_OVERFLOW(old_state)) {
David 'Digit' Turner022d3032011-12-07 14:02:17 +0100385 return EAGAIN;
386 }
387
Yabin Cuie69c2452015-02-13 16:21:25 -0800388 // Other threads are able to change the lower bits (e.g. promoting it to "contended"),
389 // but the mutex counter will not overflow. So we use atomic_fetch_add operation here.
390 // The mutex is still locked by current thread, so we don't need a release fence.
Yabin Cui17393b02015-03-21 15:08:25 -0700391 atomic_fetch_add_explicit(&mutex->state, MUTEX_COUNTER_BITS_ONE, memory_order_relaxed);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800392 return 0;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800393}
394
Yabin Cuif7969852015-04-02 17:47:48 -0700395static inline __always_inline int __recursive_or_errorcheck_mutex_wait(
396 pthread_mutex_internal_t* mutex,
397 uint16_t shared,
398 uint16_t old_state,
399 const timespec* rel_timeout) {
400// __futex_wait always waits on a 32-bit value. But state is 16-bit. For a normal mutex, the owner_tid
401// field in mutex is not used. On 64-bit devices, the __pad field in mutex is not used.
402// But when a recursive or errorcheck mutex is used on 32-bit devices, we need to add the
403// owner_tid value in the value argument for __futex_wait, otherwise we may always get EAGAIN error.
404
405#if defined(__LP64__)
406 return __futex_wait_ex(&mutex->state, shared, old_state, rel_timeout);
407
408#else
409 // This implementation works only when the layout of pthread_mutex_internal_t matches below expectation.
410 // And it is based on the assumption that Android is always in little-endian devices.
411 static_assert(offsetof(pthread_mutex_internal_t, state) == 0, "");
412 static_assert(offsetof(pthread_mutex_internal_t, owner_tid) == 2, "");
413
414 uint32_t owner_tid = atomic_load_explicit(&mutex->owner_tid, memory_order_relaxed);
415 return __futex_wait_ex(&mutex->state, shared, (owner_tid << 16) | old_state, rel_timeout);
416#endif
417}
418
Yabin Cui17393b02015-03-21 15:08:25 -0700419static int __pthread_mutex_lock_with_timeout(pthread_mutex_internal_t* mutex,
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800420 const timespec* abs_timeout_or_null, clockid_t clock) {
Yabin Cuie69c2452015-02-13 16:21:25 -0800421 uint16_t old_state = atomic_load_explicit(&mutex->state, memory_order_relaxed);
422 uint16_t mtype = (old_state & MUTEX_TYPE_MASK);
423 uint16_t shared = (old_state & MUTEX_SHARED_MASK);
Fabrice Di Meglio86418332010-03-11 14:47:47 -0800424
Yabin Cui86fc96f2015-01-29 21:50:48 -0800425 // Handle common case first.
Elliott Hughesd4e753f2013-07-16 12:45:46 -0700426 if ( __predict_true(mtype == MUTEX_TYPE_BITS_NORMAL) ) {
Yabin Cui17393b02015-03-21 15:08:25 -0700427 return __pthread_normal_mutex_lock(mutex, shared, abs_timeout_or_null, clock);
David 'Digit' Turnerba9c6f02010-03-10 16:44:08 -0800428 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700429
Yabin Cui86fc96f2015-01-29 21:50:48 -0800430 // Do we already own this recursive or error-check mutex?
Yabin Cuie69c2452015-02-13 16:21:25 -0800431 pid_t tid = __get_thread()->tid;
432 if (tid == atomic_load_explicit(&mutex->owner_tid, memory_order_relaxed)) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800433 if (mtype == MUTEX_TYPE_BITS_ERRORCHECK) {
434 return EDEADLK;
435 }
Yabin Cui17393b02015-03-21 15:08:25 -0700436 return __recursive_increment(mutex, old_state);
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800437 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700438
Yabin Cuie69c2452015-02-13 16:21:25 -0800439 const uint16_t unlocked = mtype | shared | MUTEX_STATE_BITS_UNLOCKED;
440 const uint16_t locked_uncontended = mtype | shared | MUTEX_STATE_BITS_LOCKED_UNCONTENDED;
441 const uint16_t locked_contended = mtype | shared | MUTEX_STATE_BITS_LOCKED_CONTENDED;
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700442
Yabin Cui86fc96f2015-01-29 21:50:48 -0800443 // First, if the mutex is unlocked, try to quickly acquire it.
444 // In the optimistic case where this works, set the state to locked_uncontended.
Yabin Cui17393b02015-03-21 15:08:25 -0700445 if (old_state == unlocked) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800446 // If exchanged successfully, an acquire fence is required to make
447 // all memory accesses made by other threads visible to the current CPU.
Yabin Cui17393b02015-03-21 15:08:25 -0700448 if (__predict_true(atomic_compare_exchange_strong_explicit(&mutex->state, &old_state,
Yabin Cuie69c2452015-02-13 16:21:25 -0800449 locked_uncontended, memory_order_acquire, memory_order_relaxed))) {
450 atomic_store_explicit(&mutex->owner_tid, tid, memory_order_relaxed);
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100451 return 0;
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700452 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700453 }
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100454
Brigid Smitha406ee62014-07-21 15:38:06 -0700455 ScopedTrace trace("Contending for pthread mutex");
456
Yabin Cui86fc96f2015-01-29 21:50:48 -0800457 while (true) {
Yabin Cui17393b02015-03-21 15:08:25 -0700458 if (old_state == unlocked) {
Yabin Cui86fc96f2015-01-29 21:50:48 -0800459 // NOTE: We put the state to locked_contended since we _know_ there
460 // is contention when we are in this loop. This ensures all waiters
461 // will be unlocked.
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100462
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800463 // If exchanged successfully, an acquire fence is required to make
464 // all memory accesses made by other threads visible to the current CPU.
Yabin Cui17393b02015-03-21 15:08:25 -0700465 if (__predict_true(atomic_compare_exchange_weak_explicit(&mutex->state,
Yabin Cuie69c2452015-02-13 16:21:25 -0800466 &old_state, locked_contended,
Yabin Cui86fc96f2015-01-29 21:50:48 -0800467 memory_order_acquire,
468 memory_order_relaxed))) {
Yabin Cuie69c2452015-02-13 16:21:25 -0800469 atomic_store_explicit(&mutex->owner_tid, tid, memory_order_relaxed);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800470 return 0;
471 }
472 continue;
Yabin Cui17393b02015-03-21 15:08:25 -0700473 } else if (MUTEX_STATE_BITS_IS_LOCKED_UNCONTENDED(old_state)) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800474 // We should set it to locked_contended beforing going to sleep. This can make
Yabin Cui86fc96f2015-01-29 21:50:48 -0800475 // sure waiters will be woken up eventually.
476
Yabin Cui17393b02015-03-21 15:08:25 -0700477 int new_state = MUTEX_STATE_BITS_FLIP_CONTENTION(old_state);
478 if (__predict_false(!atomic_compare_exchange_weak_explicit(&mutex->state,
479 &old_state, new_state,
Yabin Cui86fc96f2015-01-29 21:50:48 -0800480 memory_order_relaxed,
481 memory_order_relaxed))) {
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100482 continue;
483 }
Yabin Cui17393b02015-03-21 15:08:25 -0700484 old_state = new_state;
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100485 }
486
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800487 // We are in locked_contended state, sleep until someone wakes us up.
488 timespec ts;
489 timespec* rel_timeout = NULL;
490 if (abs_timeout_or_null != NULL) {
491 rel_timeout = &ts;
492 if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout_or_null, clock)) {
493 return ETIMEDOUT;
494 }
495 }
Yabin Cuif7969852015-04-02 17:47:48 -0700496 if (__recursive_or_errorcheck_mutex_wait(mutex, shared, old_state, rel_timeout) == -ETIMEDOUT) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800497 return ETIMEDOUT;
498 }
Yabin Cui17393b02015-03-21 15:08:25 -0700499 old_state = atomic_load_explicit(&mutex->state, memory_order_relaxed);
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100500 }
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800501}
502
Yabin Cui17393b02015-03-21 15:08:25 -0700503int pthread_mutex_lock(pthread_mutex_t* mutex_interface) {
504 pthread_mutex_internal_t* mutex = __get_internal_mutex(mutex_interface);
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800505
Yabin Cuie69c2452015-02-13 16:21:25 -0800506 uint16_t old_state = atomic_load_explicit(&mutex->state, memory_order_relaxed);
507 uint16_t mtype = (old_state & MUTEX_TYPE_MASK);
508 uint16_t shared = (old_state & MUTEX_SHARED_MASK);
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800509 // Avoid slowing down fast path of normal mutex lock operation.
510 if (__predict_true(mtype == MUTEX_TYPE_BITS_NORMAL)) {
Yabin Cui17393b02015-03-21 15:08:25 -0700511 if (__predict_true(__pthread_normal_mutex_trylock(mutex, shared) == 0)) {
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800512 return 0;
513 }
514 }
515 return __pthread_mutex_lock_with_timeout(mutex, NULL, 0);
516}
517
Yabin Cui17393b02015-03-21 15:08:25 -0700518int pthread_mutex_unlock(pthread_mutex_t* mutex_interface) {
519 pthread_mutex_internal_t* mutex = __get_internal_mutex(mutex_interface);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800520
Yabin Cuie69c2452015-02-13 16:21:25 -0800521 uint16_t old_state = atomic_load_explicit(&mutex->state, memory_order_relaxed);
522 uint16_t mtype = (old_state & MUTEX_TYPE_MASK);
523 uint16_t shared = (old_state & MUTEX_SHARED_MASK);
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800524
Yabin Cui86fc96f2015-01-29 21:50:48 -0800525 // Handle common case first.
Elliott Hughesd4e753f2013-07-16 12:45:46 -0700526 if (__predict_true(mtype == MUTEX_TYPE_BITS_NORMAL)) {
Yabin Cui17393b02015-03-21 15:08:25 -0700527 __pthread_normal_mutex_unlock(mutex, shared);
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800528 return 0;
529 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700530
Yabin Cui86fc96f2015-01-29 21:50:48 -0800531 // Do we already own this recursive or error-check mutex?
Yabin Cuie69c2452015-02-13 16:21:25 -0800532 pid_t tid = __get_thread()->tid;
533 if ( tid != atomic_load_explicit(&mutex->owner_tid, memory_order_relaxed) ) {
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700534 return EPERM;
Yabin Cuie69c2452015-02-13 16:21:25 -0800535 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700536
Yabin Cui86fc96f2015-01-29 21:50:48 -0800537 // If the counter is > 0, we can simply decrement it atomically.
538 // Since other threads can mutate the lower state bits (and only the
539 // lower state bits), use a compare_exchange loop to do it.
Yabin Cui17393b02015-03-21 15:08:25 -0700540 if (!MUTEX_COUNTER_BITS_IS_ZERO(old_state)) {
Yabin Cui86fc96f2015-01-29 21:50:48 -0800541 // We still own the mutex, so a release fence is not needed.
Yabin Cui17393b02015-03-21 15:08:25 -0700542 atomic_fetch_sub_explicit(&mutex->state, MUTEX_COUNTER_BITS_ONE, memory_order_relaxed);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800543 return 0;
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700544 }
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100545
Yabin Cui86fc96f2015-01-29 21:50:48 -0800546 // The counter is 0, so we'are going to unlock the mutex by resetting its
547 // state to unlocked, we need to perform a atomic_exchange inorder to read
548 // the current state, which will be locked_contended if there may have waiters
549 // to awake.
550 // A release fence is required to make previous stores visible to next
551 // lock owner threads.
Yabin Cuie69c2452015-02-13 16:21:25 -0800552 atomic_store_explicit(&mutex->owner_tid, 0, memory_order_relaxed);
553 const uint16_t unlocked = mtype | shared | MUTEX_STATE_BITS_UNLOCKED;
Yabin Cui17393b02015-03-21 15:08:25 -0700554 old_state = atomic_exchange_explicit(&mutex->state, unlocked, memory_order_release);
555 if (MUTEX_STATE_BITS_IS_LOCKED_CONTENDED(old_state)) {
556 __futex_wake_ex(&mutex->state, shared, 1);
David 'Digit' Turner88f06cd2010-03-18 17:13:41 -0700557 }
Yabin Cui86fc96f2015-01-29 21:50:48 -0800558
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700559 return 0;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800560}
561
Yabin Cui17393b02015-03-21 15:08:25 -0700562int pthread_mutex_trylock(pthread_mutex_t* mutex_interface) {
563 pthread_mutex_internal_t* mutex = __get_internal_mutex(mutex_interface);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800564
Yabin Cuie69c2452015-02-13 16:21:25 -0800565 uint16_t old_state = atomic_load_explicit(&mutex->state, memory_order_relaxed);
566 uint16_t mtype = (old_state & MUTEX_TYPE_MASK);
567 uint16_t shared = (old_state & MUTEX_SHARED_MASK);
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700568
Yabin Cuie69c2452015-02-13 16:21:25 -0800569 const uint16_t unlocked = mtype | shared | MUTEX_STATE_BITS_UNLOCKED;
570 const uint16_t locked_uncontended = mtype | shared | MUTEX_STATE_BITS_LOCKED_UNCONTENDED;
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800571
Elliott Hughes5b1111a2014-10-24 19:33:11 -0700572 // Handle common case first.
573 if (__predict_true(mtype == MUTEX_TYPE_BITS_NORMAL)) {
Yabin Cui17393b02015-03-21 15:08:25 -0700574 return __pthread_normal_mutex_trylock(mutex, shared);
David 'Digit' Turnerba9c6f02010-03-10 16:44:08 -0800575 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700576
Elliott Hughes5b1111a2014-10-24 19:33:11 -0700577 // Do we already own this recursive or error-check mutex?
578 pid_t tid = __get_thread()->tid;
Yabin Cuie69c2452015-02-13 16:21:25 -0800579 if (tid == atomic_load_explicit(&mutex->owner_tid, memory_order_relaxed)) {
Elliott Hughes5b1111a2014-10-24 19:33:11 -0700580 if (mtype == MUTEX_TYPE_BITS_ERRORCHECK) {
581 return EBUSY;
582 }
Yabin Cui17393b02015-03-21 15:08:25 -0700583 return __recursive_increment(mutex, old_state);
Elliott Hughes5b1111a2014-10-24 19:33:11 -0700584 }
David 'Digit' Turner40e6b822010-03-17 11:25:46 -0700585
Yabin Cui86fc96f2015-01-29 21:50:48 -0800586 // Same as pthread_mutex_lock, except that we don't want to wait, and
587 // the only operation that can succeed is a single compare_exchange to acquire the
588 // lock if it is released / not owned by anyone. No need for a complex loop.
Yabin Cui5b8e7cd2015-03-04 17:36:59 -0800589 // If exchanged successfully, an acquire fence is required to make
590 // all memory accesses made by other threads visible to the current CPU.
Yabin Cui17393b02015-03-21 15:08:25 -0700591 old_state = unlocked;
Yabin Cuie69c2452015-02-13 16:21:25 -0800592 if (__predict_true(atomic_compare_exchange_strong_explicit(&mutex->state, &old_state,
593 locked_uncontended,
Yabin Cui86fc96f2015-01-29 21:50:48 -0800594 memory_order_acquire,
595 memory_order_relaxed))) {
Yabin Cuie69c2452015-02-13 16:21:25 -0800596 atomic_store_explicit(&mutex->owner_tid, tid, memory_order_relaxed);
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100597 return 0;
598 }
David 'Digit' Turnere1414aa2012-01-24 15:26:54 +0100599 return EBUSY;
The Android Open Source Project1dc9e472009-03-03 19:28:35 -0800600}
601
Elliott Hughes0e714a52014-03-03 16:42:47 -0800602#if !defined(__LP64__)
Yabin Cui17393b02015-03-21 15:08:25 -0700603extern "C" int pthread_mutex_lock_timeout_np(pthread_mutex_t* mutex_interface, unsigned ms) {
Yabin Cui86fc96f2015-01-29 21:50:48 -0800604 timespec abs_timeout;
605 clock_gettime(CLOCK_MONOTONIC, &abs_timeout);
606 abs_timeout.tv_sec += ms / 1000;
607 abs_timeout.tv_nsec += (ms % 1000) * 1000000;
608 if (abs_timeout.tv_nsec >= NS_PER_S) {
609 abs_timeout.tv_sec++;
610 abs_timeout.tv_nsec -= NS_PER_S;
611 }
Elliott Hughes0e714a52014-03-03 16:42:47 -0800612
Yabin Cui17393b02015-03-21 15:08:25 -0700613 int error = __pthread_mutex_lock_with_timeout(__get_internal_mutex(mutex_interface),
614 &abs_timeout, CLOCK_MONOTONIC);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800615 if (error == ETIMEDOUT) {
616 error = EBUSY;
617 }
618 return error;
Elliott Hughes0e714a52014-03-03 16:42:47 -0800619}
620#endif
621
Yabin Cui17393b02015-03-21 15:08:25 -0700622int pthread_mutex_timedlock(pthread_mutex_t* mutex_interface, const timespec* abs_timeout) {
623 return __pthread_mutex_lock_with_timeout(__get_internal_mutex(mutex_interface),
624 abs_timeout, CLOCK_REALTIME);
Mathias Agopian7c0c3792011-09-05 23:54:55 -0700625}
626
Yabin Cui17393b02015-03-21 15:08:25 -0700627int pthread_mutex_destroy(pthread_mutex_t* mutex_interface) {
Yabin Cui86fc96f2015-01-29 21:50:48 -0800628 // Use trylock to ensure that the mutex is valid and not already locked.
Yabin Cui17393b02015-03-21 15:08:25 -0700629 int error = pthread_mutex_trylock(mutex_interface);
Yabin Cui86fc96f2015-01-29 21:50:48 -0800630 if (error != 0) {
631 return error;
632 }
Yabin Cui86fc96f2015-01-29 21:50:48 -0800633 return 0;
Mathias Agopian7c0c3792011-09-05 23:54:55 -0700634}