| /* |
| * Copyright (c) 2016 Apple Inc. All rights reserved. |
| * |
| * @APPLE_APACHE_LICENSE_HEADER_START@ |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| * |
| * @APPLE_APACHE_LICENSE_HEADER_END@ |
| */ |
| |
| /* |
| * IMPORTANT: This header file describes INTERNAL interfaces to libdispatch |
| * which are subject to change in future releases of Mac OS X. Any applications |
| * relying on these interfaces WILL break. |
| */ |
| |
| #ifndef __DISPATCH_SHIMS_LOCK__ |
| #define __DISPATCH_SHIMS_LOCK__ |
| |
| #pragma mark - platform macros |
| |
| DISPATCH_ENUM(dispatch_lock_options, uint32_t, |
| DLOCK_LOCK_NONE = 0x00000000, |
| DLOCK_LOCK_DATA_CONTENTION = 0x00010000, |
| ); |
| |
| #if TARGET_OS_MAC |
| |
| typedef mach_port_t dispatch_lock_owner; |
| typedef uint32_t dispatch_lock; |
| |
| #define DLOCK_OWNER_NULL ((dispatch_lock_owner)MACH_PORT_NULL) |
| #define DLOCK_OWNER_MASK ((dispatch_lock)0xfffffffc) |
| #define DLOCK_NOWAITERS_BIT ((dispatch_lock)0x00000001) |
| #define DLOCK_NOFAILED_TRYLOCK_BIT ((dispatch_lock)0x00000002) |
| #define _dispatch_tid_self() ((dispatch_lock_owner)_dispatch_thread_port()) |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_is_locked(dispatch_lock lock_value) |
| { |
| return (lock_value & DLOCK_OWNER_MASK) != 0; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline dispatch_lock_owner |
| _dispatch_lock_owner(dispatch_lock lock_value) |
| { |
| lock_value &= DLOCK_OWNER_MASK; |
| if (lock_value) { |
| lock_value |= DLOCK_NOWAITERS_BIT | DLOCK_NOFAILED_TRYLOCK_BIT; |
| } |
| return lock_value; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_is_locked_by(dispatch_lock lock_value, dispatch_lock_owner tid) |
| { |
| // equivalent to _dispatch_lock_owner(lock_value) == tid |
| return ((lock_value ^ tid) & DLOCK_OWNER_MASK) == 0; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_has_waiters(dispatch_lock lock_value) |
| { |
| bool nowaiters_bit = (lock_value & DLOCK_NOWAITERS_BIT); |
| return _dispatch_lock_is_locked(lock_value) != nowaiters_bit; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_has_failed_trylock(dispatch_lock lock_value) |
| { |
| return !(lock_value & DLOCK_NOFAILED_TRYLOCK_BIT); |
| } |
| |
| #elif defined(__linux__) |
| #include <linux/futex.h> |
| #include <unistd.h> |
| #include <sys/syscall.h> /* For SYS_xxx definitions */ |
| |
| typedef uint32_t dispatch_lock; |
| typedef pid_t dispatch_lock_owner; |
| |
| #define DLOCK_OWNER_NULL ((dispatch_lock_owner)0) |
| #define DLOCK_OWNER_MASK ((dispatch_lock)FUTEX_TID_MASK) |
| #define DLOCK_WAITERS_BIT ((dispatch_lock)FUTEX_WAITERS) |
| #define DLOCK_FAILED_TRYLOCK_BIT ((dispatch_lock)FUTEX_OWNER_DIED) |
| #define _dispatch_tid_self() \ |
| ((dispatch_lock_owner)(_dispatch_get_tsd_base()->tid)) |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_is_locked(dispatch_lock lock_value) |
| { |
| return (lock_value & DLOCK_OWNER_MASK) != 0; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline dispatch_lock_owner |
| _dispatch_lock_owner(dispatch_lock lock_value) |
| { |
| return (lock_value & DLOCK_OWNER_MASK); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_is_locked_by(dispatch_lock lock_value, dispatch_lock_owner tid) |
| { |
| return _dispatch_lock_owner(lock_value) == tid; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_has_waiters(dispatch_lock lock_value) |
| { |
| return (lock_value & DLOCK_WAITERS_BIT); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_lock_has_failed_trylock(dispatch_lock lock_value) |
| { |
| return !(lock_value & DLOCK_FAILED_TRYLOCK_BIT); |
| } |
| |
| #else |
| # error define _dispatch_lock encoding scheme for your platform here |
| #endif |
| |
| #if __has_include(<sys/ulock.h>) |
| #include <sys/ulock.h> |
| #endif |
| |
| #ifndef HAVE_UL_COMPARE_AND_WAIT |
| #if defined(UL_COMPARE_AND_WAIT) && DISPATCH_HOST_SUPPORTS_OSX(101200) |
| # define HAVE_UL_COMPARE_AND_WAIT 1 |
| #else |
| # define HAVE_UL_COMPARE_AND_WAIT 0 |
| #endif |
| #endif // HAVE_UL_COMPARE_AND_WAIT |
| |
| #ifndef HAVE_UL_UNFAIR_LOCK |
| #if defined(UL_UNFAIR_LOCK) && DISPATCH_HOST_SUPPORTS_OSX(101200) |
| # define HAVE_UL_UNFAIR_LOCK 1 |
| #else |
| # define HAVE_UL_UNFAIR_LOCK 0 |
| #endif |
| #endif // HAVE_UL_UNFAIR_LOCK |
| |
| #ifndef DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| #define DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK (!HAVE_UL_COMPARE_AND_WAIT && !HAVE_FUTEX) |
| #endif |
| |
| #ifndef HAVE_FUTEX |
| #ifdef __linux__ |
| #define HAVE_FUTEX 1 |
| #else |
| #define HAVE_FUTEX 0 |
| #endif |
| #endif // HAVE_FUTEX |
| |
| #if USE_MACH_SEM |
| #define DISPATCH_SEMAPHORE_VERIFY_KR(x) do { \ |
| if (unlikely((x) == KERN_INVALID_NAME)) { \ |
| DISPATCH_CLIENT_CRASH((x), "Use-after-free of dispatch_semaphore_t"); \ |
| } else if (unlikely(x)) { \ |
| DISPATCH_INTERNAL_CRASH((x), "mach semaphore API failure"); \ |
| } \ |
| } while (0) |
| #define DISPATCH_GROUP_VERIFY_KR(x) do { \ |
| if (unlikely((x) == KERN_INVALID_NAME)) { \ |
| DISPATCH_CLIENT_CRASH((x), "Use-after-free of dispatch_group_t"); \ |
| } else if (unlikely(x)) { \ |
| DISPATCH_INTERNAL_CRASH((x), "mach semaphore API failure"); \ |
| } \ |
| } while (0) |
| #elif USE_POSIX_SEM |
| #define DISPATCH_SEMAPHORE_VERIFY_RET(x) do { \ |
| if (unlikely((x) == -1)) { \ |
| DISPATCH_INTERNAL_CRASH(errno, "POSIX semaphore API failure"); \ |
| } \ |
| } while (0) |
| #endif |
| |
| #pragma mark - compare and wait |
| |
| DISPATCH_NOT_TAIL_CALLED |
| void _dispatch_wait_on_address(uint32_t volatile *address, uint32_t value, |
| dispatch_lock_options_t flags); |
| void _dispatch_wake_by_address(uint32_t volatile *address); |
| |
| #pragma mark - thread event |
| /** |
| * @typedef dispatch_thread_event_t |
| * |
| * @abstract |
| * Dispatch Thread Events are used for one-time synchronization between threads. |
| * |
| * @discussion |
| * Dispatch Thread Events are cheap synchronization points used when a thread |
| * needs to block until a certain event has happened. Dispatch Thread Event |
| * must be initialized and destroyed with _dispatch_thread_event_init() and |
| * _dispatch_thread_event_destroy(). |
| * |
| * A Dispatch Thread Event must be waited on and signaled exactly once between |
| * initialization and destruction. These objects are simpler than semaphores |
| * and do not support being signaled and waited on an arbitrary number of times. |
| * |
| * This locking primitive has no notion of ownership |
| */ |
| typedef struct dispatch_thread_event_s { |
| #if DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| union { |
| semaphore_t dte_semaphore; |
| uint32_t dte_value; |
| }; |
| #elif HAVE_UL_COMPARE_AND_WAIT || HAVE_FUTEX |
| // 1 means signalled but not waited on yet |
| // UINT32_MAX means waited on, but not signalled yet |
| // 0 is the initial and final state |
| uint32_t dte_value; |
| #elif USE_POSIX_SEM |
| sem_t dte_sem; |
| #else |
| # error define dispatch_thread_event_s for your platform |
| #endif |
| } dispatch_thread_event_s, *dispatch_thread_event_t; |
| |
| #if DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| semaphore_t _dispatch_thread_semaphore_create(void); |
| void _dispatch_thread_semaphore_dispose(void *); |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline semaphore_t |
| _dispatch_get_thread_semaphore(void) |
| { |
| semaphore_t sema = (semaphore_t)(uintptr_t) |
| _dispatch_thread_getspecific(dispatch_sema4_key); |
| if (unlikely(!sema)) { |
| return _dispatch_thread_semaphore_create(); |
| } |
| _dispatch_thread_setspecific(dispatch_sema4_key, NULL); |
| return sema; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_put_thread_semaphore(semaphore_t sema) |
| { |
| semaphore_t old_sema = (semaphore_t)(uintptr_t) |
| _dispatch_thread_getspecific(dispatch_sema4_key); |
| _dispatch_thread_setspecific(dispatch_sema4_key, (void*)(uintptr_t)sema); |
| if (unlikely(old_sema)) { |
| return _dispatch_thread_semaphore_dispose((void *)(uintptr_t)old_sema); |
| } |
| } |
| #endif |
| |
| DISPATCH_NOT_TAIL_CALLED |
| void _dispatch_thread_event_wait_slow(dispatch_thread_event_t); |
| void _dispatch_thread_event_signal_slow(dispatch_thread_event_t); |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_thread_event_init(dispatch_thread_event_t dte) |
| { |
| #if DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| if (DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK) { |
| dte->dte_semaphore = _dispatch_get_thread_semaphore(); |
| return; |
| } |
| #endif |
| #if HAVE_UL_COMPARE_AND_WAIT || HAVE_FUTEX |
| dte->dte_value = 0; |
| #elif USE_POSIX_SEM |
| int rc = sem_init(&dte->dte_sem, 0, 0); |
| DISPATCH_SEMAPHORE_VERIFY_RET(rc); |
| #endif |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_thread_event_signal(dispatch_thread_event_t dte) |
| { |
| #if DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| if (DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK) { |
| _dispatch_thread_event_signal_slow(dte); |
| return; |
| } |
| #endif |
| #if HAVE_UL_COMPARE_AND_WAIT || HAVE_FUTEX |
| if (os_atomic_inc_orig(&dte->dte_value, release) == 0) { |
| // 0 -> 1 transition doesn't need a signal |
| // force a wake even when the value is corrupt, |
| // waiters do the validation |
| return; |
| } |
| #elif USE_POSIX_SEM |
| // fallthrough |
| #endif |
| _dispatch_thread_event_signal_slow(dte); |
| } |
| |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_thread_event_wait(dispatch_thread_event_t dte) |
| { |
| #if DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| if (DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK) { |
| _dispatch_thread_event_wait_slow(dte); |
| return; |
| } |
| #endif |
| #if HAVE_UL_COMPARE_AND_WAIT || HAVE_FUTEX |
| if (os_atomic_dec(&dte->dte_value, acquire) == 0) { |
| // 1 -> 0 is always a valid transition, so we can return |
| // for any other value, go to the slowpath which checks it's not corrupt |
| return; |
| } |
| #elif USE_POSIX_SEM |
| // fallthrough |
| #endif |
| _dispatch_thread_event_wait_slow(dte); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_thread_event_destroy(dispatch_thread_event_t dte) |
| { |
| #if DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK |
| if (DISPATCH_LOCK_USE_SEMAPHORE_FALLBACK) { |
| _dispatch_put_thread_semaphore(dte->dte_semaphore); |
| return; |
| } |
| #endif |
| #if HAVE_UL_COMPARE_AND_WAIT || HAVE_FUTEX |
| // nothing to do |
| dispatch_assert(dte->dte_value == 0); |
| #elif USE_POSIX_SEM |
| int rc = sem_destroy(&dte->dte_sem); |
| DISPATCH_SEMAPHORE_VERIFY_RET(rc); |
| #endif |
| } |
| |
| #pragma mark - unfair lock |
| |
| typedef struct dispatch_unfair_lock_s { |
| dispatch_lock dul_lock; |
| } dispatch_unfair_lock_s, *dispatch_unfair_lock_t; |
| |
| DISPATCH_NOT_TAIL_CALLED |
| void _dispatch_unfair_lock_lock_slow(dispatch_unfair_lock_t l, |
| dispatch_lock_options_t options); |
| void _dispatch_unfair_lock_unlock_slow(dispatch_unfair_lock_t l, |
| dispatch_lock tid_cur); |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_unfair_lock_lock(dispatch_unfair_lock_t l) |
| { |
| dispatch_lock tid_self = _dispatch_tid_self(); |
| if (likely(os_atomic_cmpxchg(&l->dul_lock, |
| DLOCK_OWNER_NULL, tid_self, acquire))) { |
| return; |
| } |
| return _dispatch_unfair_lock_lock_slow(l, DLOCK_LOCK_NONE); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_unfair_lock_trylock(dispatch_unfair_lock_t l, |
| dispatch_lock_owner *owner) |
| { |
| dispatch_lock tid_old, tid_new, tid_self = _dispatch_tid_self(); |
| |
| os_atomic_rmw_loop(&l->dul_lock, tid_old, tid_new, acquire, { |
| if (likely(!_dispatch_lock_is_locked(tid_old))) { |
| tid_new = tid_self; |
| } else { |
| #ifdef DLOCK_NOFAILED_TRYLOCK_BIT |
| tid_new = tid_old & ~DLOCK_NOFAILED_TRYLOCK_BIT; |
| #else |
| tid_new = tid_old | DLOCK_FAILED_TRYLOCK_BIT; |
| #endif |
| } |
| }); |
| if (owner) *owner = _dispatch_lock_owner(tid_new); |
| return !_dispatch_lock_is_locked(tid_old); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_unfair_lock_tryunlock(dispatch_unfair_lock_t l) |
| { |
| dispatch_lock tid_old, tid_new; |
| |
| os_atomic_rmw_loop(&l->dul_lock, tid_old, tid_new, release, { |
| #ifdef DLOCK_NOFAILED_TRYLOCK_BIT |
| if (likely(tid_old & DLOCK_NOFAILED_TRYLOCK_BIT)) { |
| tid_new = DLOCK_OWNER_NULL; |
| } else { |
| tid_new = tid_old | DLOCK_NOFAILED_TRYLOCK_BIT; |
| } |
| #else |
| if (likely(!(tid_old & DLOCK_FAILED_TRYLOCK_BIT))) { |
| tid_new = DLOCK_OWNER_NULL; |
| } else { |
| tid_new = tid_old & ~DLOCK_FAILED_TRYLOCK_BIT; |
| } |
| #endif |
| }); |
| if (unlikely(tid_new)) { |
| // unlock failed, renew the lock, which needs an acquire barrier |
| os_atomic_thread_fence(acquire); |
| return false; |
| } |
| if (unlikely(_dispatch_lock_has_waiters(tid_old))) { |
| _dispatch_unfair_lock_unlock_slow(l, tid_old); |
| } |
| return true; |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_unfair_lock_unlock_had_failed_trylock(dispatch_unfair_lock_t l) |
| { |
| dispatch_lock tid_cur, tid_self = _dispatch_tid_self(); |
| #if HAVE_FUTEX |
| if (likely(os_atomic_cmpxchgv(&l->dul_lock, |
| tid_self, DLOCK_OWNER_NULL, &tid_cur, release))) { |
| return false; |
| } |
| #else |
| tid_cur = os_atomic_xchg(&l->dul_lock, DLOCK_OWNER_NULL, release); |
| if (likely(tid_cur == tid_self)) return false; |
| #endif |
| _dispatch_unfair_lock_unlock_slow(l, tid_cur); |
| return _dispatch_lock_has_failed_trylock(tid_cur); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_unfair_lock_unlock(dispatch_unfair_lock_t l) |
| { |
| (void)_dispatch_unfair_lock_unlock_had_failed_trylock(l); |
| } |
| |
| #pragma mark - gate lock |
| |
| #if HAVE_UL_UNFAIR_LOCK || HAVE_FUTEX |
| #define DISPATCH_GATE_USE_FOR_DISPATCH_ONCE 1 |
| #else |
| #define DISPATCH_GATE_USE_FOR_DISPATCH_ONCE 0 |
| #endif |
| |
| #define DLOCK_GATE_UNLOCKED ((dispatch_lock)0) |
| |
| #define DLOCK_ONCE_UNLOCKED ((dispatch_once_t)0) |
| #define DLOCK_ONCE_DONE (~(dispatch_once_t)0) |
| |
| typedef struct dispatch_gate_s { |
| dispatch_lock dgl_lock; |
| } dispatch_gate_s, *dispatch_gate_t; |
| |
| typedef struct dispatch_once_gate_s { |
| union { |
| dispatch_gate_s dgo_gate; |
| dispatch_once_t dgo_once; |
| }; |
| } dispatch_once_gate_s, *dispatch_once_gate_t; |
| |
| DISPATCH_NOT_TAIL_CALLED |
| void _dispatch_gate_wait_slow(dispatch_gate_t l, dispatch_lock value, |
| uint32_t flags); |
| void _dispatch_gate_broadcast_slow(dispatch_gate_t l, dispatch_lock tid_cur); |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_gate_tryenter(dispatch_gate_t l) |
| { |
| dispatch_lock tid_self = _dispatch_tid_self(); |
| return likely(os_atomic_cmpxchg(&l->dgl_lock, |
| DLOCK_GATE_UNLOCKED, tid_self, acquire)); |
| } |
| |
| #define _dispatch_gate_wait(l, flags) \ |
| _dispatch_gate_wait_slow(l, DLOCK_GATE_UNLOCKED, flags) |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_gate_broadcast(dispatch_gate_t l) |
| { |
| dispatch_lock tid_cur, tid_self = _dispatch_tid_self(); |
| tid_cur = os_atomic_xchg(&l->dgl_lock, DLOCK_GATE_UNLOCKED, release); |
| if (likely(tid_cur == tid_self)) return; |
| _dispatch_gate_broadcast_slow(l, tid_cur); |
| } |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline bool |
| _dispatch_once_gate_tryenter(dispatch_once_gate_t l) |
| { |
| dispatch_once_t tid_self = (dispatch_once_t)_dispatch_tid_self(); |
| return likely(os_atomic_cmpxchg(&l->dgo_once, |
| DLOCK_ONCE_UNLOCKED, tid_self, acquire)); |
| } |
| |
| #define _dispatch_once_gate_wait(l) \ |
| _dispatch_gate_wait_slow(&(l)->dgo_gate, (dispatch_lock)DLOCK_ONCE_DONE, \ |
| DLOCK_LOCK_NONE) |
| |
| DISPATCH_ALWAYS_INLINE |
| static inline void |
| _dispatch_once_gate_broadcast(dispatch_once_gate_t l) |
| { |
| dispatch_once_t tid_cur, tid_self = (dispatch_once_t)_dispatch_tid_self(); |
| // see once.c for explanation about this trick |
| os_atomic_maximally_synchronizing_barrier(); |
| // above assumed to contain release barrier |
| tid_cur = os_atomic_xchg(&l->dgo_once, DLOCK_ONCE_DONE, relaxed); |
| if (likely(tid_cur == tid_self)) return; |
| _dispatch_gate_broadcast_slow(&l->dgo_gate, (dispatch_lock)tid_cur); |
| } |
| |
| #endif // __DISPATCH_SHIMS_LOCK__ |