1 //===------------------------- atomic.cpp ---------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include <__config> 10 #ifndef _LIBCPP_HAS_NO_THREADS 11 12 #include <climits> 13 #include <atomic> 14 #include <functional> 15 16 #ifdef __linux__ 17 18 #include <unistd.h> 19 #include <linux/futex.h> 20 #include <sys/syscall.h> 21 22 #else // <- Add other operating systems here 23 24 // Baseline needs no new headers 25 26 #endif 27 28 _LIBCPP_BEGIN_NAMESPACE_STD 29 30 #ifdef __linux__ 31 32 static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr, 33 __cxx_contention_t __val) 34 { 35 static constexpr timespec __timeout = { 2, 0 }; 36 syscall(SYS_futex, __ptr, FUTEX_WAIT_PRIVATE, __val, &__timeout, 0, 0); 37 } 38 39 static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile* __ptr, 40 bool __notify_one) 41 { 42 syscall(SYS_futex, __ptr, FUTEX_WAKE_PRIVATE, __notify_one ? 1 : INT_MAX, 0, 0, 0); 43 } 44 45 #elif defined(__APPLE__) && defined(_LIBCPP_USE_ULOCK) 46 47 extern "C" int __ulock_wait(uint32_t operation, void *addr, uint64_t value, 48 uint32_t timeout); /* timeout is specified in microseconds */ 49 extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value); 50 51 #define UL_COMPARE_AND_WAIT 1 52 #define ULF_WAKE_ALL 0x00000100 53 54 static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr, 55 __cxx_contention_t __val) 56 { 57 __ulock_wait(UL_COMPARE_AND_WAIT, 58 const_cast<__cxx_atomic_contention_t*>(__ptr), __val, 0); 59 } 60 61 static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile* __ptr, 62 bool __notify_one) 63 { 64 __ulock_wake(UL_COMPARE_AND_WAIT | (__notify_one ? 0 : ULF_WAKE_ALL), 65 const_cast<__cxx_atomic_contention_t*>(__ptr), 0); 66 } 67 68 #else // <- Add other operating systems here 69 70 // Baseline is just a timed backoff 71 72 static void __libcpp_platform_wait_on_address(__cxx_atomic_contention_t const volatile* __ptr, 73 __cxx_contention_t __val) 74 { 75 __libcpp_thread_poll_with_backoff([=]() -> bool { 76 return !__cxx_nonatomic_compare_equal(__cxx_atomic_load(__ptr, memory_order_relaxed), __val); 77 }, __libcpp_timed_backoff_policy()); 78 } 79 80 static void __libcpp_platform_wake_by_address(__cxx_atomic_contention_t const volatile*, bool) { } 81 82 #endif // __linux__ 83 84 static constexpr size_t __libcpp_contention_table_size = (1 << 8); /* < there's no magic in this number */ 85 86 struct alignas(64) /* aim to avoid false sharing */ __libcpp_contention_table_entry 87 { 88 __cxx_atomic_contention_t __contention_state; 89 __cxx_atomic_contention_t __platform_state; 90 inline constexpr __libcpp_contention_table_entry() : 91 __contention_state(0), __platform_state(0) { } 92 }; 93 94 static __libcpp_contention_table_entry __libcpp_contention_table[ __libcpp_contention_table_size ]; 95 96 static hash<void const volatile*> __libcpp_contention_hasher; 97 98 static __libcpp_contention_table_entry* __libcpp_contention_state(void const volatile * p) 99 { 100 return &__libcpp_contention_table[__libcpp_contention_hasher(p) & (__libcpp_contention_table_size - 1)]; 101 } 102 103 /* Given an atomic to track contention and an atomic to actually wait on, which may be 104 the same atomic, we try to detect contention to avoid spuriously calling the platform. */ 105 106 static void __libcpp_contention_notify(__cxx_atomic_contention_t volatile* __contention_state, 107 __cxx_atomic_contention_t const volatile* __platform_state, 108 bool __notify_one) 109 { 110 if(0 != __cxx_atomic_load(__contention_state, memory_order_seq_cst)) 111 // We only call 'wake' if we consumed a contention bit here. 112 __libcpp_platform_wake_by_address(__platform_state, __notify_one); 113 } 114 static __cxx_contention_t __libcpp_contention_monitor_for_wait(__cxx_atomic_contention_t volatile* __contention_state, 115 __cxx_atomic_contention_t const volatile* __platform_state) 116 { 117 // We will monitor this value. 118 return __cxx_atomic_load(__platform_state, memory_order_acquire); 119 } 120 static void __libcpp_contention_wait(__cxx_atomic_contention_t volatile* __contention_state, 121 __cxx_atomic_contention_t const volatile* __platform_state, 122 __cxx_contention_t __old_value) 123 { 124 __cxx_atomic_fetch_add(__contention_state, __cxx_contention_t(1), memory_order_seq_cst); 125 // We sleep as long as the monitored value hasn't changed. 126 __libcpp_platform_wait_on_address(__platform_state, __old_value); 127 __cxx_atomic_fetch_sub(__contention_state, __cxx_contention_t(1), memory_order_release); 128 } 129 130 /* When the incoming atomic is the wrong size for the platform wait size, need to 131 launder the value sequence through an atomic from our table. */ 132 133 static void __libcpp_atomic_notify(void const volatile* __location) 134 { 135 auto const __entry = __libcpp_contention_state(__location); 136 // The value sequence laundering happens on the next line below. 137 __cxx_atomic_fetch_add(&__entry->__platform_state, __cxx_contention_t(1), memory_order_release); 138 __libcpp_contention_notify(&__entry->__contention_state, 139 &__entry->__platform_state, 140 false /* when laundering, we can't handle notify_one */); 141 } 142 _LIBCPP_EXPORTED_FROM_ABI 143 void __cxx_atomic_notify_one(void const volatile* __location) 144 { __libcpp_atomic_notify(__location); } 145 _LIBCPP_EXPORTED_FROM_ABI 146 void __cxx_atomic_notify_all(void const volatile* __location) 147 { __libcpp_atomic_notify(__location); } 148 _LIBCPP_EXPORTED_FROM_ABI 149 __cxx_contention_t __libcpp_atomic_monitor(void const volatile* __location) 150 { 151 auto const __entry = __libcpp_contention_state(__location); 152 return __libcpp_contention_monitor_for_wait(&__entry->__contention_state, &__entry->__platform_state); 153 } 154 _LIBCPP_EXPORTED_FROM_ABI 155 void __libcpp_atomic_wait(void const volatile* __location, __cxx_contention_t __old_value) 156 { 157 auto const __entry = __libcpp_contention_state(__location); 158 __libcpp_contention_wait(&__entry->__contention_state, &__entry->__platform_state, __old_value); 159 } 160 161 /* When the incoming atomic happens to be the platform wait size, we still need to use the 162 table for the contention detection, but we can use the atomic directly for the wait. */ 163 164 _LIBCPP_EXPORTED_FROM_ABI 165 void __cxx_atomic_notify_one(__cxx_atomic_contention_t const volatile* __location) 166 { 167 __libcpp_contention_notify(&__libcpp_contention_state(__location)->__contention_state, __location, true); 168 } 169 _LIBCPP_EXPORTED_FROM_ABI 170 void __cxx_atomic_notify_all(__cxx_atomic_contention_t const volatile* __location) 171 { 172 __libcpp_contention_notify(&__libcpp_contention_state(__location)->__contention_state, __location, false); 173 } 174 _LIBCPP_EXPORTED_FROM_ABI 175 __cxx_contention_t __libcpp_atomic_monitor(__cxx_atomic_contention_t const volatile* __location) 176 { 177 return __libcpp_contention_monitor_for_wait(&__libcpp_contention_state(__location)->__contention_state, __location); 178 } 179 _LIBCPP_EXPORTED_FROM_ABI 180 void __libcpp_atomic_wait(__cxx_atomic_contention_t const volatile* __location, __cxx_contention_t __old_value) 181 { 182 __libcpp_contention_wait(&__libcpp_contention_state(__location)->__contention_state, __location, __old_value); 183 } 184 185 _LIBCPP_END_NAMESPACE_STD 186 187 #endif //_LIBCPP_HAS_NO_THREADS 188