+#pragma mark firstfit
+
+PTHREAD_ALWAYS_INLINE
+static inline int
+_pthread_mutex_firstfit_unlock_updatebits(_pthread_mutex *mutex,
+ uint32_t *flagsp, uint32_t **mutexp, uint32_t *lvalp, uint32_t *uvalp)
+{
+ uint32_t flags = mutex->mtxopts.value & ~_PTHREAD_MTX_OPT_NOTIFY;
+ bool kernel_wake;
+
+ mutex_seq *seqaddr;
+ MUTEX_GETSEQ_ADDR(mutex, &seqaddr);
+
+ mutex_seq oldseq, newseq;
+ mutex_seq_load(seqaddr, &oldseq);
+
+ uint64_t *tidaddr;
+ MUTEX_GETTID_ADDR(mutex, &tidaddr);
+ uint64_t oldtid;
+
+ int res = _pthread_mutex_unlock_handle_options(mutex, tidaddr);
+ if (res > 0) {
+ // Valid recursive unlock
+ if (flagsp) {
+ *flagsp = flags;
+ }
+ PLOCKSTAT_MUTEX_RELEASE((pthread_mutex_t *)mutex, 1);
+ return 0;
+ } else if (res < 0) {
+ PLOCKSTAT_MUTEX_ERROR((pthread_mutex_t *)mutex, -res);
+ return -res;
+ }
+
+ do {
+ newseq = oldseq;
+ oldtid = os_atomic_load(tidaddr, relaxed);
+ // More than one kernel waiter means we need to do a wake.
+ kernel_wake = diff_genseq(oldseq.lgenval, oldseq.ugenval) > 0;
+ newseq.lgenval &= ~PTH_RWL_EBIT;
+
+ if (kernel_wake) {
+ // Going to the kernel post-unlock removes a single waiter unlock
+ // from the mutex counts.
+ newseq.ugenval += PTHRW_INC;
+ }
+
+ if (oldtid != 0) {
+ if (!os_atomic_cmpxchg(tidaddr, oldtid, 0, relaxed)) {
+ return _pthread_mutex_corruption_abort(mutex);
+ }
+ }
+ } while (!mutex_seq_atomic_cmpxchgv(seqaddr, &oldseq, &newseq, release));
+
+ PTHREAD_TRACE(psynch_ffmutex_unlock_updatebits, mutex, oldseq.lgenval,
+ newseq.lgenval, newseq.ugenval);
+
+ if (kernel_wake) {
+ // We choose to return this out via flags because the condition
+ // variable also uses this to determine whether to do a kernel wake
+ // when beginning a cvwait.
+ flags |= _PTHREAD_MTX_OPT_NOTIFY;
+ }
+ if (lvalp) {
+ *lvalp = newseq.lgenval;
+ }
+ if (uvalp) {
+ *uvalp = newseq.ugenval;
+ }
+ if (mutexp) {
+ *mutexp = (uint32_t *)mutex;
+ }
+ if (flagsp) {
+ *flagsp = flags;
+ }
+ return 0;
+}
+
+PTHREAD_NOEXPORT PTHREAD_NOINLINE
+static int
+_pthread_mutex_firstfit_wake(_pthread_mutex *mutex, mutex_seq newseq,
+ uint32_t flags)
+{
+ PTHREAD_TRACE(psynch_ffmutex_wake, mutex, newseq.lgenval, newseq.ugenval,
+ 0);
+ int res = __psynch_mutexdrop(mutex, newseq.lgenval, newseq.ugenval, 0,
+ flags);
+
+ if (res == -1) {
+ res = errno;
+ if (res == EINTR) {
+ res = 0;
+ }
+ if (res != 0) {
+ PTHREAD_ABORT("__psynch_mutexdrop failed with error %d", res);
+ }
+ return res;
+ }
+ return 0;
+}
+
+PTHREAD_NOEXPORT PTHREAD_NOINLINE
+int
+_pthread_mutex_firstfit_unlock_slow(_pthread_mutex *mutex)
+{
+ mutex_seq newseq;
+ uint32_t flags;
+ int res;
+
+ res = _pthread_mutex_firstfit_unlock_updatebits(mutex, &flags, NULL,
+ &newseq.lgenval, &newseq.ugenval);
+ if (res != 0) return res;
+
+ if (flags & _PTHREAD_MTX_OPT_NOTIFY) {
+ return _pthread_mutex_firstfit_wake(mutex, newseq, flags);
+ }
+ return 0;
+}
+
+PTHREAD_ALWAYS_INLINE
+static bool
+_pthread_mutex_firstfit_lock_updatebits(_pthread_mutex *mutex, uint64_t selfid,
+ mutex_seq *newseqp)
+{
+ bool gotlock;
+
+ mutex_seq *seqaddr;
+ MUTEX_GETSEQ_ADDR(mutex, &seqaddr);
+
+ mutex_seq oldseq, newseq;
+ mutex_seq_load(seqaddr, &oldseq);
+
+ uint64_t *tidaddr;
+ MUTEX_GETTID_ADDR(mutex, &tidaddr);
+
+ PTHREAD_TRACE(psynch_ffmutex_lock_updatebits | DBG_FUNC_START, mutex,
+ oldseq.lgenval, oldseq.ugenval, 0);
+
+ do {
+ newseq = oldseq;
+ gotlock = is_rwl_ebit_clear(oldseq.lgenval);
+
+ if (gotlock) {
+ // If we see the E-bit cleared, we should just attempt to take it.
+ newseq.lgenval |= PTH_RWL_EBIT;
+ } else {
+ // If we failed to get the lock then we need to put ourselves back
+ // in the queue of waiters. The previous unlocker that woke us out
+ // of the kernel consumed the S-count for our previous wake. So
+ // take another ticket on L and go back in the kernel to sleep.
+ newseq.lgenval += PTHRW_INC;
+ }
+ } while (!mutex_seq_atomic_cmpxchgv(seqaddr, &oldseq, &newseq, acquire));
+
+ if (gotlock) {
+ os_atomic_store(tidaddr, selfid, relaxed);
+ }
+
+ PTHREAD_TRACE(psynch_ffmutex_lock_updatebits | DBG_FUNC_END, mutex,
+ newseq.lgenval, newseq.ugenval, 0);
+
+ if (newseqp) {
+ *newseqp = newseq;
+ }
+ return gotlock;
+}
+
+PTHREAD_NOINLINE
+static int
+_pthread_mutex_firstfit_lock_wait(_pthread_mutex *mutex, mutex_seq newseq,
+ uint64_t oldtid)
+{
+ uint64_t *tidaddr;
+ MUTEX_GETTID_ADDR(mutex, &tidaddr);
+ uint64_t selfid = _pthread_selfid_direct();
+
+ PLOCKSTAT_MUTEX_BLOCK((pthread_mutex_t *)mutex);
+ do {
+ uint32_t uval;
+ do {
+ PTHREAD_TRACE(psynch_ffmutex_wait | DBG_FUNC_START, mutex,
+ newseq.lgenval, newseq.ugenval, mutex->mtxopts.value);
+ uval = __psynch_mutexwait(mutex, newseq.lgenval, newseq.ugenval,
+ oldtid, mutex->mtxopts.value);
+ PTHREAD_TRACE(psynch_ffmutex_wait | DBG_FUNC_END, mutex,
+ uval, 0, 0);
+ oldtid = os_atomic_load(tidaddr, relaxed);
+ } while (uval == (uint32_t)-1);
+ } while (!_pthread_mutex_firstfit_lock_updatebits(mutex, selfid, &newseq));
+ PLOCKSTAT_MUTEX_BLOCKED((pthread_mutex_t *)mutex, BLOCK_SUCCESS_PLOCKSTAT);
+
+ return 0;
+}
+
+PTHREAD_NOEXPORT PTHREAD_NOINLINE
+int
+_pthread_mutex_firstfit_lock_slow(_pthread_mutex *mutex, bool trylock)
+{
+ int res, recursive = 0;
+
+ mutex_seq *seqaddr;
+ MUTEX_GETSEQ_ADDR(mutex, &seqaddr);
+
+ mutex_seq oldseq, newseq;
+ mutex_seq_load(seqaddr, &oldseq);
+
+ uint64_t *tidaddr;
+ MUTEX_GETTID_ADDR(mutex, &tidaddr);
+ uint64_t oldtid, selfid = _pthread_selfid_direct();
+
+ res = _pthread_mutex_lock_handle_options(mutex, trylock, tidaddr);
+ if (res > 0) {
+ recursive = 1;
+ res = 0;
+ goto out;
+ } else if (res < 0) {
+ res = -res;
+ goto out;
+ }
+
+ PTHREAD_TRACE(psynch_ffmutex_lock_updatebits | DBG_FUNC_START, mutex,
+ oldseq.lgenval, oldseq.ugenval, 0);
+
+ bool gotlock;
+ do {
+ newseq = oldseq;
+ oldtid = os_atomic_load(tidaddr, relaxed);
+
+ gotlock = is_rwl_ebit_clear(oldseq.lgenval);
+ if (trylock && !gotlock) {
+ // We still want to perform the CAS here, even though it won't
+ // do anything so that it fails if someone unlocked while we were
+ // in the loop
+ } else if (gotlock) {
+ // In first-fit, getting the lock simply adds the E-bit
+ newseq.lgenval |= PTH_RWL_EBIT;
+ } else {
+ // Failed to get the lock, increment the L-val and go to
+ // the kernel to sleep
+ newseq.lgenval += PTHRW_INC;
+ }
+ } while (!mutex_seq_atomic_cmpxchgv(seqaddr, &oldseq, &newseq, acquire));
+
+ PTHREAD_TRACE(psynch_ffmutex_lock_updatebits | DBG_FUNC_END, mutex,
+ newseq.lgenval, newseq.ugenval, 0);
+
+ if (gotlock) {
+ os_atomic_store(tidaddr, selfid, relaxed);
+ res = 0;
+ PTHREAD_TRACE(psynch_mutex_ulock, mutex, newseq.lgenval,
+ newseq.ugenval, selfid);
+ } else if (trylock) {
+ res = EBUSY;
+ PTHREAD_TRACE(psynch_mutex_utrylock_failed, mutex, newseq.lgenval,
+ newseq.ugenval, oldtid);
+ } else {
+ PTHREAD_TRACE(psynch_mutex_ulock | DBG_FUNC_START, mutex,
+ newseq.lgenval, newseq.ugenval, oldtid);
+ res = _pthread_mutex_firstfit_lock_wait(mutex, newseq, oldtid);
+ PTHREAD_TRACE(psynch_mutex_ulock | DBG_FUNC_END, mutex,
+ newseq.lgenval, newseq.ugenval, oldtid);
+ }
+
+ if (res == 0 && _pthread_mutex_is_recursive(mutex)) {
+ mutex->mtxopts.options.lock_count = 1;
+ }
+
+out:
+#if PLOCKSTAT
+ if (res == 0) {
+ PLOCKSTAT_MUTEX_ACQUIRE((pthread_mutex_t *)mutex, recursive, 0);
+ } else {
+ PLOCKSTAT_MUTEX_ERROR((pthread_mutex_t *)mutex, res);
+ }
+#endif
+ return res;
+}
+
+#pragma mark fast path
+
+PTHREAD_NOEXPORT PTHREAD_NOINLINE
+int
+_pthread_mutex_droplock(_pthread_mutex *mutex, uint32_t *flagsp,
+ uint32_t **pmtxp, uint32_t *mgenp, uint32_t *ugenp)
+{
+ if (_pthread_mutex_is_fairshare(mutex)) {
+ return _pthread_mutex_fairshare_unlock_updatebits(mutex, flagsp,
+ pmtxp, mgenp, ugenp);
+ }
+ return _pthread_mutex_firstfit_unlock_updatebits(mutex, flagsp, pmtxp,
+ mgenp, ugenp);
+}
+
+PTHREAD_NOEXPORT PTHREAD_NOINLINE
+int
+_pthread_mutex_lock_init_slow(_pthread_mutex *mutex, bool trylock)
+{
+ int res;
+
+ res = _pthread_mutex_check_init(mutex);
+ if (res != 0) return res;
+
+ if (os_unlikely(_pthread_mutex_is_fairshare(mutex))) {
+ return _pthread_mutex_fairshare_lock_slow(mutex, trylock);
+ }
+ return _pthread_mutex_firstfit_lock_slow(mutex, trylock);
+}
+
+PTHREAD_NOEXPORT PTHREAD_NOINLINE
+static int
+_pthread_mutex_unlock_init_slow(_pthread_mutex *mutex)
+{
+ int res;
+
+ // Initialize static mutexes for compatibility with misbehaving
+ // applications (unlock should not be the first operation on a mutex).
+ res = _pthread_mutex_check_init(mutex);
+ if (res != 0) return res;
+
+ if (os_unlikely(_pthread_mutex_is_fairshare(mutex))) {
+ return _pthread_mutex_fairshare_unlock_slow(mutex);
+ }
+ return _pthread_mutex_firstfit_unlock_slow(mutex);
+}
+
+PTHREAD_NOEXPORT_VARIANT
+int
+pthread_mutex_unlock(pthread_mutex_t *omutex)
+{
+ _pthread_mutex *mutex = (_pthread_mutex *)omutex;
+ if (os_unlikely(!_pthread_mutex_check_signature_fast(mutex))) {
+ return _pthread_mutex_unlock_init_slow(mutex);
+ }
+
+ if (os_unlikely(_pthread_mutex_is_fairshare(mutex))) {
+ return _pthread_mutex_fairshare_unlock(mutex);
+ }
+
+#if ENABLE_USERSPACE_TRACE
+ return _pthread_mutex_firstfit_unlock_slow(mutex);
+#elif PLOCKSTAT
+ if (PLOCKSTAT_MUTEX_RELEASE_ENABLED() || PLOCKSTAT_MUTEX_ERROR_ENABLED()) {
+ return _pthread_mutex_firstfit_unlock_slow(mutex);
+ }
+#endif
+
+ /*
+ * This is the first-fit fast path. The fairshare fast-ish path is in
+ * _pthread_mutex_firstfit_unlock()
+ */
+ uint64_t *tidaddr;
+ MUTEX_GETTID_ADDR(mutex, &tidaddr);
+
+ mutex_seq *seqaddr;
+ MUTEX_GETSEQ_ADDR(mutex, &seqaddr);
+
+ mutex_seq oldseq, newseq;
+ mutex_seq_load(seqaddr, &oldseq);
+
+ // We're giving up the mutex one way or the other, so go ahead and
+ // update the owner to 0 so that once the CAS below succeeds, there
+ // is no stale ownership information. If the CAS of the seqaddr
+ // fails, we may loop, but it's still valid for the owner to be
+ // SWITCHING/0
+ os_atomic_store(tidaddr, 0, relaxed);
+
+ do {
+ newseq = oldseq;
+
+ if (diff_genseq(oldseq.lgenval, oldseq.ugenval) == 0) {
+ // No outstanding waiters in kernel, we can simply drop the E-bit
+ // and return.
+ newseq.lgenval &= ~PTH_RWL_EBIT;
+ } else {
+ return _pthread_mutex_firstfit_unlock_slow(mutex);
+ }
+ } while (os_unlikely(!mutex_seq_atomic_cmpxchgv(seqaddr, &oldseq, &newseq,
+ release)));
+
+ return 0;
+}
+
+PTHREAD_ALWAYS_INLINE
+static inline int
+_pthread_mutex_firstfit_lock(pthread_mutex_t *omutex, bool trylock)
+{
+ _pthread_mutex *mutex = (_pthread_mutex *)omutex;
+ if (os_unlikely(!_pthread_mutex_check_signature_fast(mutex))) {
+ return _pthread_mutex_lock_init_slow(mutex, trylock);
+ }
+
+ if (os_unlikely(_pthread_mutex_is_fairshare(mutex))) {
+ return _pthread_mutex_fairshare_lock(mutex, trylock);
+ }
+
+#if ENABLE_USERSPACE_TRACE
+ return _pthread_mutex_firstfit_lock_slow(mutex, trylock);
+#elif PLOCKSTAT
+ if (PLOCKSTAT_MUTEX_ACQUIRE_ENABLED() || PLOCKSTAT_MUTEX_ERROR_ENABLED()) {
+ return _pthread_mutex_firstfit_lock_slow(mutex, trylock);
+ }
+#endif
+
+ /*
+ * This is the first-fit fast path. The fairshare fast-ish path is in
+ * _pthread_mutex_firstfit_lock()
+ */
+ uint64_t *tidaddr;
+ MUTEX_GETTID_ADDR(mutex, &tidaddr);
+ uint64_t selfid = _pthread_selfid_direct();
+
+ mutex_seq *seqaddr;
+ MUTEX_GETSEQ_ADDR(mutex, &seqaddr);
+
+ mutex_seq oldseq, newseq;
+ mutex_seq_load(seqaddr, &oldseq);
+
+ if (os_unlikely(oldseq.lgenval & PTH_RWL_EBIT)) {
+ return _pthread_mutex_firstfit_lock_slow(mutex, trylock);
+ }
+
+ bool gotlock;
+ do {
+ newseq = oldseq;
+ gotlock = is_rwl_ebit_clear(oldseq.lgenval);
+
+ if (trylock && !gotlock) {
+ // A trylock on a held lock will fail immediately. But since
+ // we did not load the sequence words atomically, perform a
+ // no-op CAS64 to ensure that nobody has unlocked concurrently.
+ } else if (os_likely(gotlock)) {
+ // In first-fit, getting the lock simply adds the E-bit
+ newseq.lgenval |= PTH_RWL_EBIT;
+ } else {
+ return _pthread_mutex_firstfit_lock_slow(mutex, trylock);
+ }
+ } while (os_unlikely(!mutex_seq_atomic_cmpxchgv(seqaddr, &oldseq, &newseq,
+ acquire)));
+
+ if (os_likely(gotlock)) {
+ os_atomic_store(tidaddr, selfid, relaxed);
+ return 0;
+ } else if (trylock) {
+ return EBUSY;
+ } else {
+ __builtin_trap();
+ }
+}
+
+PTHREAD_NOEXPORT_VARIANT
+int
+pthread_mutex_lock(pthread_mutex_t *mutex)
+{
+ return _pthread_mutex_firstfit_lock(mutex, false);
+}
+
+PTHREAD_NOEXPORT_VARIANT
+int
+pthread_mutex_trylock(pthread_mutex_t *mutex)
+{
+ return _pthread_mutex_firstfit_lock(mutex, true);
+}
+
projects / apple / libpthread.git / blobdiff